QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#291114 | #2892. 合法序列 | MoRanSky | AC ✓ | 453ms | 12104kb | C++23 | 1.1kb | 2023-12-26 04:54:43 | 2023-12-26 04:54:44 |
Judging History
answer
#include <iostream>
#include <cstdio>
#include <cstring>
typedef long long LL;
using namespace std;
const int S = 1 << 16, T = 1 << 4, P = 998244353;
int n, K, f[S][T], s, g[S][T];
int main() {
scanf("%d%d", &n, &K); s = (1 << K) - 1;
int t = 1 << K;
for (int i = 0; i < (1 << t); i++) {
bool ok = true;
for (int j = 0; j + K - 1 < t; j++) {
int s = 0;
for (int k = j; k < j + K; k++)
s = s * 2 + (i >> k & 1);
if (!(i >> s & 1)) {
ok = false; break;
}
}
if (!ok) continue;
int s = 0;
for (int k = t - K; k < t; k++)
s = s * 2 + (i >> k & 1);
f[i][s] ++;
}
for (int i = 0; i < n - t; i++) {
memcpy(g, f, sizeof g);
memset(f, 0, sizeof f);
for (int i = 0; i < (1 << t); i++) {
for (int j = 0; j < (1 << K); j++) {
if (!g[i][j]) continue;
int b = (j << 1) & s;
if (i >> b & 1) (f[i][b] += g[i][j]) %= P;
if (i >> (b + 1) & 1) (f[i][b + 1] += g[i][j]) %= P;
}
}
}
int ans = 0;
for (int i = 0; i < (1 << t); i++) {
for (int j = 0; j < (1 << K); j++) {
(ans += f[i][j]) %= P;
}
}
printf("%d\n", ans);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 5912kb
input:
2 1
output:
1
result:
ok single line: '1'
Test #2:
score: 0
Accepted
time: 0ms
memory: 12048kb
input:
10 3
output:
27
result:
ok single line: '27'
Test #3:
score: 0
Accepted
time: 0ms
memory: 12104kb
input:
11 3
output:
46
result:
ok single line: '46'
Test #4:
score: 0
Accepted
time: 199ms
memory: 12100kb
input:
500 3
output:
402086823
result:
ok single line: '402086823'
Test #5:
score: 0
Accepted
time: 5ms
memory: 7952kb
input:
16 4
output:
268
result:
ok single line: '268'
Test #6:
score: 0
Accepted
time: 3ms
memory: 12024kb
input:
17 4
output:
520
result:
ok single line: '520'
Test #7:
score: 0
Accepted
time: 4ms
memory: 12020kb
input:
18 4
output:
939
result:
ok single line: '939'
Test #8:
score: 0
Accepted
time: 9ms
memory: 12024kb
input:
19 4
output:
1634
result:
ok single line: '1634'
Test #9:
score: 0
Accepted
time: 3ms
memory: 11920kb
input:
20 4
output:
2678
result:
ok single line: '2678'
Test #10:
score: 0
Accepted
time: 453ms
memory: 11956kb
input:
500 4
output:
905810545
result:
ok single line: '905810545'
Test #11:
score: 0
Accepted
time: 63ms
memory: 12044kb
input:
156 3
output:
158348364
result:
ok single line: '158348364'
Test #12:
score: 0
Accepted
time: 0ms
memory: 12040kb
input:
3 1
output:
2
result:
ok single line: '2'
Test #13:
score: 0
Accepted
time: 168ms
memory: 12052kb
input:
419 1
output:
309520444
result:
ok single line: '309520444'
Test #14:
score: 0
Accepted
time: 62ms
memory: 12016kb
input:
148 1
output:
981388471
result:
ok single line: '981388471'
Test #15:
score: 0
Accepted
time: 82ms
memory: 12056kb
input:
208 1
output:
17788609
result:
ok single line: '17788609'
Test #16:
score: 0
Accepted
time: 291ms
memory: 12052kb
input:
325 4
output:
534470501
result:
ok single line: '534470501'
Test #17:
score: 0
Accepted
time: 188ms
memory: 12052kb
input:
478 1
output:
275981743
result:
ok single line: '275981743'
Test #18:
score: 0
Accepted
time: 177ms
memory: 11968kb
input:
437 3
output:
448979837
result:
ok single line: '448979837'
Test #19:
score: 0
Accepted
time: 105ms
memory: 11964kb
input:
260 3
output:
249722589
result:
ok single line: '249722589'
Test #20:
score: 0
Accepted
time: 166ms
memory: 12028kb
input:
406 2
output:
762498912
result:
ok single line: '762498912'
Test #21:
score: 0
Accepted
time: 138ms
memory: 11920kb
input:
348 2
output:
718553190
result:
ok single line: '718553190'
Test #22:
score: 0
Accepted
time: 137ms
memory: 11960kb
input:
350 1
output:
496751081
result:
ok single line: '496751081'
Test #23:
score: 0
Accepted
time: 202ms
memory: 12028kb
input:
500 1
output:
154029661
result:
ok single line: '154029661'
Test #24:
score: 0
Accepted
time: 311ms
memory: 12048kb
input:
344 4
output:
864324256
result:
ok single line: '864324256'
Test #25:
score: 0
Accepted
time: 51ms
memory: 12040kb
input:
127 3
output:
306783420
result:
ok single line: '306783420'
Test #26:
score: 0
Accepted
time: 145ms
memory: 12100kb
input:
170 4
output:
138463737
result:
ok single line: '138463737'
Test #27:
score: 0
Accepted
time: 77ms
memory: 11952kb
input:
199 3
output:
988988696
result:
ok single line: '988988696'
Test #28:
score: 0
Accepted
time: 80ms
memory: 12100kb
input:
206 3
output:
992080398
result:
ok single line: '992080398'
Test #29:
score: 0
Accepted
time: 27ms
memory: 12104kb
input:
82 2
output:
755922348
result:
ok single line: '755922348'
Test #30:
score: 0
Accepted
time: 139ms
memory: 12096kb
input:
351 2
output:
285073312
result:
ok single line: '285073312'
Test #31:
score: 0
Accepted
time: 109ms
memory: 12012kb
input:
274 1
output:
609866862
result:
ok single line: '609866862'
Test #32:
score: 0
Accepted
time: 165ms
memory: 11960kb
input:
416 3
output:
49398792
result:
ok single line: '49398792'
Test #33:
score: 0
Accepted
time: 1ms
memory: 5812kb
input:
4 2
output:
2
result:
ok single line: '2'
Test #34:
score: 0
Accepted
time: 0ms
memory: 12012kb
input:
5 2
output:
4
result:
ok single line: '4'
Test #35:
score: 0
Accepted
time: 0ms
memory: 11916kb
input:
6 2
output:
7
result:
ok single line: '7'
Test #36:
score: 0
Accepted
time: 200ms
memory: 12036kb
input:
500 2
output:
255888452
result:
ok single line: '255888452'
Test #37:
score: 0
Accepted
time: 1ms
memory: 5916kb
input:
8 3
output:
8
result:
ok single line: '8'
Test #38:
score: 0
Accepted
time: 3ms
memory: 12016kb
input:
9 3
output:
15
result:
ok single line: '15'