Task: | Bit Strings |
Sender: | .* |
Submission time: | 2019-05-25 14:27:33 +0300 |
Language: | C++ |
Status: | READY |
Result: | WRONG ANSWER |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.03 s | details |
#2 | ACCEPTED | 0.02 s | details |
#3 | ACCEPTED | 0.02 s | details |
#4 | ACCEPTED | 0.03 s | details |
#5 | ACCEPTED | 0.03 s | details |
#6 | ACCEPTED | 0.01 s | details |
#7 | ACCEPTED | 0.02 s | details |
#8 | ACCEPTED | 0.01 s | details |
#9 | ACCEPTED | 0.02 s | details |
#10 | ACCEPTED | 0.02 s | details |
#11 | WRONG ANSWER | 0.04 s | details |
#12 | ACCEPTED | 0.01 s | details |
#13 | WRONG ANSWER | 0.05 s | details |
#14 | WRONG ANSWER | 0.06 s | details |
#15 | ACCEPTED | 0.05 s | details |
#16 | WRONG ANSWER | 0.04 s | details |
#17 | WRONG ANSWER | 0.05 s | details |
#18 | WRONG ANSWER | 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;}cout << s<<endl;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;//haku(0, "");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][1] %= M;}cout << d[n][1]+d[n][0];}
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: WRONG ANSWER
input |
---|
654321 123456 |
correct output |
---|
796245691 |
user output |
---|
1796245698 |
Test 12
Verdict: ACCEPTED
input |
---|
1000000 1 |
correct output |
---|
1 |
user output |
---|
1 |
Test 13
Verdict: WRONG ANSWER
input |
---|
1000000 10 |
correct output |
---|
256933600 |
user output |
---|
1256933607 |
Test 14
Verdict: WRONG ANSWER
input |
---|
1000000 100 |
correct output |
---|
142013415 |
user output |
---|
1142013422 |
Test 15
Verdict: ACCEPTED
input |
---|
1000000 1000 |
correct output |
---|
899626120 |
user output |
---|
899626120 |
Test 16
Verdict: WRONG ANSWER
input |
---|
1000000 10000 |
correct output |
---|
374265948 |
user output |
---|
1374265955 |
Test 17
Verdict: WRONG ANSWER
input |
---|
1000000 100000 |
correct output |
---|
388134512 |
user output |
---|
1388134519 |
Test 18
Verdict: WRONG ANSWER
input |
---|
1000000 1000000 |
correct output |
---|
235042058 |
user output |
---|
1235042065 |