QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#830014 | #2892. 合法序列 | lyx | AC ✓ | 59ms | 3968kb | C++14 | 955b | 2024-12-24 15:28:52 | 2024-12-24 15:28:56 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
int n,k;
int a[23];
int f[503][10];
int ans=0;
void add(int &x,int y){x+=y;if(x>=mod)x-=mod;}
void dfs(int x)
{
if(x>=16||x>=n)
{
for(int i=0;i<=15;i++)
{
if(i+k-1>min(n-1,15))continue;
int s=0;
for(int j=i;j<=i+k-1;j++)s=s*2+a[j];
if(a[s]==0)return;
}
if(n<=16){add(ans,1);return;}
int w=0;
for(int i=15-k+2;i<=15;i++)w=w*2+a[i];
for(int i=15;i<=n;i++)
{
for(int j=0;j<(1<<k-1);j++)f[i][j]=0;
}
f[15][w]=1;
for(int i=15;i<n-1;i++)
{
for(int j=0;j<(1<<k-1);j++)
{
for(int p=0;p<2;p++)
{
int v=j*2+p;
if(a[v]==0)continue;
add(f[i+1][v&((1<<k-1)-1)],f[i][j]);
}
}
}
int lt=ans;
for(int j=0;j<(1<<k-1);j++)add(ans,f[n-1][j]);
return;
}
a[x]=0;dfs(x+1);
a[x]=1;dfs(x+1);
}
int main()
{
scanf("%d %d",&n,&k);
dfs(0);
printf("%d",ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3888kb
input:
2 1
output:
1
result:
ok single line: '1'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
10 3
output:
27
result:
ok single line: '27'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3872kb
input:
11 3
output:
46
result:
ok single line: '46'
Test #4:
score: 0
Accepted
time: 5ms
memory: 3800kb
input:
500 3
output:
402086823
result:
ok single line: '402086823'
Test #5:
score: 0
Accepted
time: 1ms
memory: 3692kb
input:
16 4
output:
268
result:
ok single line: '268'
Test #6:
score: 0
Accepted
time: 1ms
memory: 3944kb
input:
17 4
output:
520
result:
ok single line: '520'
Test #7:
score: 0
Accepted
time: 1ms
memory: 3876kb
input:
18 4
output:
939
result:
ok single line: '939'
Test #8:
score: 0
Accepted
time: 1ms
memory: 3872kb
input:
19 4
output:
1634
result:
ok single line: '1634'
Test #9:
score: 0
Accepted
time: 1ms
memory: 3756kb
input:
20 4
output:
2678
result:
ok single line: '2678'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3876kb
input:
500 4
output:
905810545
result:
ok single line: '905810545'
Test #11:
score: 0
Accepted
time: 2ms
memory: 3876kb
input:
156 3
output:
158348364
result:
ok single line: '158348364'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3944kb
input:
3 1
output:
2
result:
ok single line: '2'
Test #13:
score: 0
Accepted
time: 49ms
memory: 3960kb
input:
419 1
output:
309520444
result:
ok single line: '309520444'
Test #14:
score: 0
Accepted
time: 17ms
memory: 3948kb
input:
148 1
output:
981388471
result:
ok single line: '981388471'
Test #15:
score: 0
Accepted
time: 24ms
memory: 3816kb
input:
208 1
output:
17788609
result:
ok single line: '17788609'
Test #16:
score: 0
Accepted
time: 2ms
memory: 3808kb
input:
325 4
output:
534470501
result:
ok single line: '534470501'
Test #17:
score: 0
Accepted
time: 52ms
memory: 3888kb
input:
478 1
output:
275981743
result:
ok single line: '275981743'
Test #18:
score: 0
Accepted
time: 5ms
memory: 3772kb
input:
437 3
output:
448979837
result:
ok single line: '448979837'
Test #19:
score: 0
Accepted
time: 3ms
memory: 3868kb
input:
260 3
output:
249722589
result:
ok single line: '249722589'
Test #20:
score: 0
Accepted
time: 15ms
memory: 3800kb
input:
406 2
output:
762498912
result:
ok single line: '762498912'
Test #21:
score: 0
Accepted
time: 13ms
memory: 3964kb
input:
348 2
output:
718553190
result:
ok single line: '718553190'
Test #22:
score: 0
Accepted
time: 41ms
memory: 3880kb
input:
350 1
output:
496751081
result:
ok single line: '496751081'
Test #23:
score: 0
Accepted
time: 59ms
memory: 3808kb
input:
500 1
output:
154029661
result:
ok single line: '154029661'
Test #24:
score: 0
Accepted
time: 2ms
memory: 3960kb
input:
344 4
output:
864324256
result:
ok single line: '864324256'
Test #25:
score: 0
Accepted
time: 2ms
memory: 3960kb
input:
127 3
output:
306783420
result:
ok single line: '306783420'
Test #26:
score: 0
Accepted
time: 1ms
memory: 3884kb
input:
170 4
output:
138463737
result:
ok single line: '138463737'
Test #27:
score: 0
Accepted
time: 2ms
memory: 3736kb
input:
199 3
output:
988988696
result:
ok single line: '988988696'
Test #28:
score: 0
Accepted
time: 3ms
memory: 3956kb
input:
206 3
output:
992080398
result:
ok single line: '992080398'
Test #29:
score: 0
Accepted
time: 3ms
memory: 3912kb
input:
82 2
output:
755922348
result:
ok single line: '755922348'
Test #30:
score: 0
Accepted
time: 13ms
memory: 3812kb
input:
351 2
output:
285073312
result:
ok single line: '285073312'
Test #31:
score: 0
Accepted
time: 33ms
memory: 3880kb
input:
274 1
output:
609866862
result:
ok single line: '609866862'
Test #32:
score: 0
Accepted
time: 5ms
memory: 3888kb
input:
416 3
output:
49398792
result:
ok single line: '49398792'
Test #33:
score: 0
Accepted
time: 0ms
memory: 3812kb
input:
4 2
output:
2
result:
ok single line: '2'
Test #34:
score: 0
Accepted
time: 0ms
memory: 3732kb
input:
5 2
output:
4
result:
ok single line: '4'
Test #35:
score: 0
Accepted
time: 0ms
memory: 3876kb
input:
6 2
output:
7
result:
ok single line: '7'
Test #36:
score: 0
Accepted
time: 19ms
memory: 3968kb
input:
500 2
output:
255888452
result:
ok single line: '255888452'
Test #37:
score: 0
Accepted
time: 0ms
memory: 3880kb
input:
8 3
output:
8
result:
ok single line: '8'
Test #38:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
9 3
output:
15
result:
ok single line: '15'