QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#22947	#2892. 合法序列	gsh^#	AC ✓	10ms	3740kb	C++20	858b	2022-03-11 11:47:51	2022-04-30 02:10:02

Judging History

你现在查看的是最新测评结果

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2022-04-30 02:10:02]
评测

测评结果：AC
用时：10ms
内存：3740kb

查看

[2022-03-11 11:47:51]
提交

answer

#include<algorithm>
#include<iostream>
#include<vector>
#include<cstdio>
using namespace std;
#define For(i,l,r) for(int i=l;i<=r;i++)
#define FOR(i,l,r) for(int i=l;i>=r;i--)
#define P 998244353
#define MAXN 501
int N,K,f[MAXN][16],ans;
int get(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x*f;}
int main()
{
	cin>>N>>K;int x=1<<K;
	For(s,0,(1<<x)-1)
	{
		vector<int>a(x+1);For(i,0,x-1)a[x-1-i]=s>>i&1;
		bool flag=1;int now=0;For(i,0,K-1)now=now<<1|a[i];
		For(i,K,x){if(!a[now]){flag=0;break;}now=(now<<1|a[i])&(x-1);}if(!flag)continue;
		For(i,0,N)For(j,0,15)f[i][j]=0;f[x-1][s&x-1]=1;
		For(i,x-1,N-2)For(j,0,x-1)For(k,0,1){int t=(j<<1|k)&x-1;if(a[t])f[i+1][t]=(f[i+1][t]+f[i][j])%P;}
		For(i,0,x-1)ans=(ans+f[N-1][i])%P;
	}
	cout<<ans<<'\n';
}

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 3ms

memory: 3572kb

input:

2 1

output:

result:

ok single line: '1'

Test #2:

score: 0

Accepted

time: 3ms

memory: 3648kb

input:

10 3

output:

result:

ok single line: '27'

Test #3:

score: 0

Accepted

time: 3ms

memory: 3572kb

input:

11 3

output:

result:

ok single line: '46'

Test #4:

score: 0

Accepted

time: 0ms

memory: 3696kb

input:

500 3

output:

402086823

result:

ok single line: '402086823'

Test #5:

score: 0

Accepted

time: 1ms

memory: 3588kb

input:

16 4

output:

result:

ok single line: '268'

Test #6:

score: 0

Accepted

time: 5ms

memory: 3684kb

input:

17 4

output:

result:

ok single line: '520'

Test #7:

score: 0

Accepted

time: 2ms

memory: 3656kb

input:

18 4

output:

result:

ok single line: '939'

Test #8:

score: 0

Accepted

time: 5ms

memory: 3656kb

input:

19 4

output:

result:

ok single line: '1634'

Test #9:

score: 0

Accepted

time: 5ms

memory: 3560kb

input:

20 4

output:

result:

ok single line: '2678'

Test #10:

score: 0

Accepted

time: 10ms

memory: 3620kb

input:

500 4

output:

905810545

result:

ok single line: '905810545'

Test #11:

score: 0

Accepted

time: 3ms

memory: 3584kb

input:

156 3

output:

158348364

result:

ok single line: '158348364'

Test #12:

score: 0

Accepted

time: 3ms

memory: 3584kb

input:

3 1

output:

result:

ok single line: '2'

Test #13:

score: 0

Accepted

time: 3ms

memory: 3612kb

input:

419 1

output:

309520444

result:

ok single line: '309520444'

Test #14:

score: 0

Accepted

time: 3ms

memory: 3656kb

input:

148 1

output:

981388471

result:

ok single line: '981388471'

Test #15:

score: 0

Accepted

time: 3ms

memory: 3556kb

input:

208 1

output:

17788609

result:

ok single line: '17788609'

Test #16:

score: 0

Accepted

time: 3ms

memory: 3472kb

input:

325 4

output:

534470501

result:

ok single line: '534470501'

Test #17:

score: 0

Accepted

time: 3ms

memory: 3708kb

input:

478 1

output:

275981743

result:

ok single line: '275981743'

Test #18:

score: 0

Accepted

time: 0ms

memory: 3628kb

input:

437 3

output:

448979837

result:

ok single line: '448979837'

Test #19:

score: 0

Accepted

time: 0ms

memory: 3556kb

input:

260 3

output:

249722589

result:

ok single line: '249722589'

Test #20:

score: 0

Accepted

time: 1ms

memory: 3596kb

input:

406 2

output:

762498912

result:

ok single line: '762498912'

Test #21:

score: 0

Accepted

time: 3ms

memory: 3616kb

input:

348 2

output:

718553190

result:

ok single line: '718553190'

Test #22:

score: 0

Accepted

time: 3ms

memory: 3740kb

input:

350 1

output:

496751081

result:

ok single line: '496751081'

Test #23:

score: 0

Accepted

time: 3ms

memory: 3548kb

input:

500 1

output:

154029661

result:

ok single line: '154029661'

Test #24:

score: 0

Accepted

time: 9ms

memory: 3580kb

input:

344 4

output:

864324256

result:

ok single line: '864324256'

Test #25:

score: 0

Accepted

time: 0ms

memory: 3460kb

input:

127 3

output:

306783420

result:

ok single line: '306783420'

Test #26:

score: 0

Accepted

time: 3ms

memory: 3464kb

input:

170 4

output:

138463737

result:

ok single line: '138463737'

Test #27:

score: 0

Accepted

time: 2ms

memory: 3668kb

input:

199 3

output:

988988696

result:

ok single line: '988988696'

Test #28:

score: 0

Accepted

time: 0ms

memory: 3608kb

input:

206 3

output:

992080398

result:

ok single line: '992080398'

Test #29:

score: 0

Accepted

time: 2ms

memory: 3456kb

input:

82 2

output:

755922348

result:

ok single line: '755922348'

Test #30:

score: 0

Accepted

time: 1ms

memory: 3560kb

input:

351 2

output:

285073312

result:

ok single line: '285073312'

Test #31:

score: 0

Accepted

time: 2ms

memory: 3608kb

input:

274 1

output:

609866862

result:

ok single line: '609866862'

Test #32:

score: 0

Accepted

time: 3ms

memory: 3612kb

input:

416 3

output:

49398792

result:

ok single line: '49398792'

Test #33:

score: 0

Accepted

time: 3ms

memory: 3596kb

input:

4 2

output:

result:

ok single line: '2'

Test #34:

score: 0

Accepted

time: 3ms

memory: 3588kb

input:

5 2

output:

result:

ok single line: '4'

Test #35:

score: 0

Accepted

time: 3ms

memory: 3580kb

input:

6 2

output:

result:

ok single line: '7'

Test #36:

score: 0

Accepted

time: 3ms

memory: 3568kb

input:

500 2

output:

255888452

result:

ok single line: '255888452'

Test #37:

score: 0

Accepted

time: 3ms

memory: 3520kb

input:

8 3

output:

result:

ok single line: '8'

Test #38:

score: 0

Accepted

time: 0ms

memory: 3560kb

input:

9 3

output:

result:

ok single line: '15'