CSES - Putka Open 2020 – 2/5 - Results
Submission details
Task:Torni
Sender:Gomhog
Submission time:2020-09-25 19:09:56 +0300
Language:C++ (C++11)
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED15
#2ACCEPTED41
#3ACCEPTED44
Test results
testverdicttimegroup
#1ACCEPTED0.02 s1, 2, 3details
#2ACCEPTED0.02 s2, 3details
#3ACCEPTED0.02 s3details

Code

#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
#define F first
#define S second
using namespace std;
ll dp[1010101][2];
const ll M=1e9+7;
void dfs() {
dp[1][0]=1;
dp[1][1]=1;
for (int j=2;j<1010101;j++) {
dp[j][0]=(4*dp[j-1][0]+dp[j-1][1])%M;
dp[j][1]=(dp[j-1][0]+2*dp[j-1][1])%M;
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
dfs();
int tst;
cin>>tst;
for (int t=0;t<tst;t++) {
int n;
cin>>n;
cout<<(dp[n][0]+dp[n][1])%M<<"\n";
}
}

Test details

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

input
10
1
2
3
4
...

correct output
2
8
34
148
650
...

user output
2
8
34
148
650
...

Test 2

Group: 2, 3

Verdict: ACCEPTED

input
100
1
2
3
4
...

correct output
2
8
34
148
650
...

user output
2
8
34
148
650
...
Truncated

Test 3

Group: 3

Verdict: ACCEPTED

input
100
996306
650655
896240
821967
...

correct output
87350005
606189151
122595036
193572715
227926807
...

user output
87350005
606189151
122595036
193572715
227926807
...
Truncated