Submission #2,905

2023-02-02 13:21:08

cpp11

Accepted 50/50

18ms

16364 KiB

#include <bits/stdc++.h>

using namespace std;

const int MOD = 20210108;

int main(){


    int n; cin >> n;
    vector<int> dp = {1, 2, 4};

    for (int i = 3; i <= n; i++){
        dp.push_back((2*dp[i-1] + 2*dp[i-3]) % MOD);
    }

    cout << dp[n];

    // dp(n) = 2*dp(n-1) + 2*dp(n-3)

    return 0;
}

	Sum	Test	Verdict		Time	Memory
base	50/50
		1	Accepted	0/0	3ms	1960 KiB
		2	Accepted	0/0	3ms	2136 KiB
		3	Accepted	3/3	3ms	2332 KiB
		4	Accepted	3/3	2ms	2400 KiB
		5	Accepted	4/4	2ms	2612 KiB
		6	Accepted	4/4	3ms	2708 KiB
		7	Accepted	4/4	18ms	15336 KiB
		8	Accepted	4/4	4ms	5032 KiB
		9	Accepted	4/4	3ms	3356 KiB
		10	Accepted	4/4	3ms	3520 KiB
		11	Accepted	4/4	6ms	6852 KiB
		12	Accepted	4/4	17ms	16096 KiB
		13	Accepted	4/4	17ms	16364 KiB
		14	Accepted	4/4	7ms	7176 KiB
		15	Accepted	2/2	3ms	4104 KiB
		16	Accepted	2/2	2ms	4176 KiB