Task: | Bit Strings |
Sender: | .* |
Submission time: | 2019-05-25 14:31:50 +0300 |
Language: | C++ |
Status: | READY |
Result: | ACCEPTED |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.02 s | details |
#2 | ACCEPTED | 0.02 s | details |
#3 | ACCEPTED | 0.02 s | details |
#4 | ACCEPTED | 0.03 s | details |
#5 | ACCEPTED | 0.02 s | details |
#6 | ACCEPTED | 0.01 s | details |
#7 | ACCEPTED | 0.02 s | details |
#8 | ACCEPTED | 0.02 s | details |
#9 | ACCEPTED | 0.02 s | details |
#10 | ACCEPTED | 0.02 s | details |
#11 | ACCEPTED | 0.05 s | details |
#12 | ACCEPTED | 0.02 s | details |
#13 | ACCEPTED | 0.06 s | details |
#14 | ACCEPTED | 0.06 s | details |
#15 | ACCEPTED | 0.06 s | details |
#16 | ACCEPTED | 0.06 s | details |
#17 | ACCEPTED | 0.05 s | details |
#18 | ACCEPTED | 0.05 s | details |
Code
#include <bits/stdc++.h> #define ll long long #define ld long double #define ull unsigned long long #define M 1000000007 #define N (1<<18) #define P complex<long long> #define X real() #define Y imag() using namespace std; ll n, k, d[1010101][2], cntt; void haku(int len, string s) { if(len == n) { char ed = 'G'; int cnt = 0; for(auto u:s) { if(u == ed) { cnt++; } else { cnt = 1; ed = u; } if(cnt == k && ed == '0') return; } cntt++; } else { haku(len+1, s+"1"); haku(len+1, s+"0"); } } int main() { cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0); cin >> n >> k; if(k == 1) { cout << 1; exit(0); } else { } d[0][0] = 1; d[0][1] = (k==1)?0:1; d[1][0] = 1; d[1][1] = (k==1)?0:1; for(int i=2; i<=n; i++) { d[i][0] = d[i-1][0]+d[i-1][1]; d[i][1] = d[i-1][0]+d[i-1][1]; d[i][0] %= M; d[i][1] %= M; if(i-k>=0) d[i][0] -= d[i-k][1]; d[i][0] %= M; d[i][0] += M; d[i][0] %= M; d[i][0] += M; d[i][0] %= M; d[i][1] %= M; } cout << (d[n][1]+d[n][0])%M; }
Test details
Test 1
Verdict: ACCEPTED
input |
---|
1 1 |
correct output |
---|
1 |
user output |
---|
1 |
Test 2
Verdict: ACCEPTED
input |
---|
2 1 |
correct output |
---|
1 |
user output |
---|
1 |
Test 3
Verdict: ACCEPTED
input |
---|
2 2 |
correct output |
---|
3 |
user output |
---|
3 |
Test 4
Verdict: ACCEPTED
input |
---|
3 1 |
correct output |
---|
1 |
user output |
---|
1 |
Test 5
Verdict: ACCEPTED
input |
---|
3 2 |
correct output |
---|
5 |
user output |
---|
5 |
Test 6
Verdict: ACCEPTED
input |
---|
3 3 |
correct output |
---|
7 |
user output |
---|
7 |
Test 7
Verdict: ACCEPTED
input |
---|
4 1 |
correct output |
---|
1 |
user output |
---|
1 |
Test 8
Verdict: ACCEPTED
input |
---|
4 2 |
correct output |
---|
8 |
user output |
---|
8 |
Test 9
Verdict: ACCEPTED
input |
---|
4 3 |
correct output |
---|
13 |
user output |
---|
13 |
Test 10
Verdict: ACCEPTED
input |
---|
4 4 |
correct output |
---|
15 |
user output |
---|
15 |
Test 11
Verdict: ACCEPTED
input |
---|
654321 123456 |
correct output |
---|
796245691 |
user output |
---|
796245691 |
Test 12
Verdict: ACCEPTED
input |
---|
1000000 1 |
correct output |
---|
1 |
user output |
---|
1 |
Test 13
Verdict: ACCEPTED
input |
---|
1000000 10 |
correct output |
---|
256933600 |
user output |
---|
256933600 |
Test 14
Verdict: ACCEPTED
input |
---|
1000000 100 |
correct output |
---|
142013415 |
user output |
---|
142013415 |
Test 15
Verdict: ACCEPTED
input |
---|
1000000 1000 |
correct output |
---|
899626120 |
user output |
---|
899626120 |
Test 16
Verdict: ACCEPTED
input |
---|
1000000 10000 |
correct output |
---|
374265948 |
user output |
---|
374265948 |
Test 17
Verdict: ACCEPTED
input |
---|
1000000 100000 |
correct output |
---|
388134512 |
user output |
---|
388134512 |
Test 18
Verdict: ACCEPTED
input |
---|
1000000 1000000 |
correct output |
---|
235042058 |
user output |
---|
235042058 |