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

Code

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = (ll)1e9 + 7;
ll modPow(ll a, ll b) {
if (b & 1) return a * modPow(a, b-1) % MOD;
if (b == 0) return 1;
return modPow(a*a % MOD, b / 2);
}
const int N = 1e6;
ll pref1[N+1]; // Count if starts with two 1-wide pieces
ll pref2[N+1]; // Count if starts with one 2-wide piece
ll ans[N+1];
void solve() {
int n;
cin >> n;
cout << ans[n] << '\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
// DP1[n] = \sum_{i = 1}^{n} (2^{i} DP1[n-i] + 2^{i-1} DP2[n-i])
// DP2[n] = \sum_{i = 1}^{n} DP1[n-i] + DP2[n-i]
ll two_inv = modPow(2, MOD - 2);
ll two_pow = 2, inv_pow = two_inv;
pref1[0] = two_inv;
pref2[0] = 1;
ans[0] = 1;
for (int i = 1; i <= N; ++i) {
ll dp1 = (two_pow * pref1[i-1]) % MOD;
ll dp2 = pref2[i-1];
ll nxt_inv_pow = (inv_pow * two_inv) % MOD;
pref1[i] = (pref1[i-1] + inv_pow * dp1 + nxt_inv_pow * dp2) % MOD;
pref2[i] = (pref2[i-1] + dp1 + dp2) % MOD;
ans[i] = (dp1 + dp2) % MOD;
two_pow = (2 * two_pow) % MOD;
inv_pow = nxt_inv_pow;
}
int t;
cin >> t;
for (int ti = 0; ti < t; ++ti) solve();
}

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