159202025-03-20 19:36:5742Toronyépítés (80 pont)cpp17Elfogadva 80/801ms508 KiB
#include <iostream>
#include <unordered_map>
using namespace std;

const int mod = 20210108;
unordered_map<int, int> d = {{0, 1}, {1, 3}, {2, 10}, {3, 33}, {4, 109}, {5, 360}};

int f(int n) {
    if (d.find(n) != d.end()) {
        return d[n];
    }
    if (n % 2 == 0) {
        int cur = (1LL * f(n / 2) * f(n / 2) + 1LL * f(n / 2 - 1) * f(n / 2 - 1)) % mod;
        d[n] = cur;
        return cur;
    }
    int cur = (1LL * f(n / 2) * (f(n / 2 - 1) + f(n / 2 + 1))) % mod;
    d[n] = cur;
    return cur;
}

int main() {
    int N;
    cin >> N;
    cout << f(N) << endl;
    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base80/80
1Elfogadva0/01ms508 KiB
2Elfogadva0/01ms316 KiB
3Elfogadva4/41ms316 KiB
4Elfogadva4/41ms316 KiB
5Elfogadva5/51ms316 KiB
6Elfogadva5/51ms316 KiB
7Elfogadva6/61ms316 KiB
8Elfogadva6/61ms316 KiB
9Elfogadva7/71ms384 KiB
10Elfogadva7/71ms316 KiB
11Elfogadva8/81ms500 KiB
12Elfogadva8/81ms316 KiB
13Elfogadva8/81ms328 KiB
14Elfogadva8/81ms316 KiB
15Elfogadva2/21ms508 KiB
16Elfogadva2/21ms400 KiB