QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#812624#2892. 合法序列Fake_Jowaire#AC ✓4ms3748kbC++141.2kb2024-12-13 17:10:312024-12-13 17:10:32

Judging History

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

  • [2024-12-13 17:10:32]
  • 评测
  • 测评结果:AC
  • 用时:4ms
  • 内存:3748kb
  • [2024-12-13 17:10:31]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

const int N=505,H=998244353;
int n,m,tot=0,f[N][20],ans=0;

int adc(int a,int b){return a+b>=H?a+b-H:a+b;}
int dec(int a,int b){return a<b?a-b+H:a-b;}
int mul(int a,int b){return 1ll*a*b%H;}
void add(int &a,int b){a=adc(a,b);}
void del(int &a,int b){a=dec(a,b);}

int qpow(int a,int b=H-2){
  int res=1;
  while(b){if(b&1) res=mul(res,a);a=mul(a,a),b>>=1;}
  return res;
}

int main(){
  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  cin>>n>>m;
  tot=(1<<m);
  for(int S=0;S<(1<<tot);S++){
  	bool fl=true;
  	for(int i=0;i<=tot-m;i++){
  	  int nw=0;
  	  for(int j=0;j<m;j++) nw=(nw<<1)+(S>>(i+j)&1);
  	  if(!(S>>nw&1)){fl=false;break;}
	}
	if(!fl) continue;
	
	int cur=0;
	for(int i=0;i<(1<<(m-1));i++) f[tot-1][i]=0;
	for(int i=tot-m+1;i<tot;i++) cur=(cur<<1)+(S>>i&1);
	f[tot-1][cur]=1;
	for(int i=tot;i<n;i++){
	  memset(f[i],0,sizeof(f[i]));
	  for(int j=0;j<(1<<(m-1));j++){
	    if(f[i-1][j]){
	      for(int k:{0,1}) if(S>>((j<<1)+k)&1) add(f[i][((j<<1)+k)&((1<<(m-1))-1)],f[i-1][j]);
	    }
      }
    }
    for(int i=0;i<(1<<(m-1));i++) add(ans,f[n-1][i]);
  }
  cout<<ans;
  return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3612kb

input:

2 1

output:

1

result:

ok single line: '1'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3560kb

input:

10 3

output:

27

result:

ok single line: '27'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3624kb

input:

11 3

output:

46

result:

ok single line: '46'

Test #4:

score: 0
Accepted
time: 1ms
memory: 3748kb

input:

500 3

output:

402086823

result:

ok single line: '402086823'

Test #5:

score: 0
Accepted
time: 1ms
memory: 3592kb

input:

16 4

output:

268

result:

ok single line: '268'

Test #6:

score: 0
Accepted
time: 1ms
memory: 3584kb

input:

17 4

output:

520

result:

ok single line: '520'

Test #7:

score: 0
Accepted
time: 1ms
memory: 3644kb

input:

18 4

output:

939

result:

ok single line: '939'

Test #8:

score: 0
Accepted
time: 1ms
memory: 3552kb

input:

19 4

output:

1634

result:

ok single line: '1634'

Test #9:

score: 0
Accepted
time: 1ms
memory: 3560kb

input:

20 4

output:

2678

result:

ok single line: '2678'

Test #10:

score: 0
Accepted
time: 4ms
memory: 3668kb

input:

500 4

output:

905810545

result:

ok single line: '905810545'

Test #11:

score: 0
Accepted
time: 1ms
memory: 3628kb

input:

156 3

output:

158348364

result:

ok single line: '158348364'

Test #12:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

3 1

output:

2

result:

ok single line: '2'

Test #13:

score: 0
Accepted
time: 0ms
memory: 3684kb

input:

419 1

output:

309520444

result:

ok single line: '309520444'

Test #14:

score: 0
Accepted
time: 0ms
memory: 3656kb

input:

148 1

output:

981388471

result:

ok single line: '981388471'

Test #15:

score: 0
Accepted
time: 0ms
memory: 3596kb

input:

208 1

output:

17788609

result:

ok single line: '17788609'

Test #16:

score: 0
Accepted
time: 3ms
memory: 3648kb

input:

325 4

output:

534470501

result:

ok single line: '534470501'

Test #17:

score: 0
Accepted
time: 0ms
memory: 3668kb

input:

478 1

output:

275981743

result:

ok single line: '275981743'

Test #18:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

437 3

output:

448979837

result:

ok single line: '448979837'

Test #19:

score: 0
Accepted
time: 0ms
memory: 3636kb

input:

260 3

output:

249722589

result:

ok single line: '249722589'

Test #20:

score: 0
Accepted
time: 0ms
memory: 3592kb

input:

406 2

output:

762498912

result:

ok single line: '762498912'

Test #21:

score: 0
Accepted
time: 0ms
memory: 3600kb

input:

348 2

output:

718553190

result:

ok single line: '718553190'

Test #22:

score: 0
Accepted
time: 0ms
memory: 3664kb

input:

350 1

output:

496751081

result:

ok single line: '496751081'

Test #23:

score: 0
Accepted
time: 0ms
memory: 3680kb

input:

500 1

output:

154029661

result:

ok single line: '154029661'

Test #24:

score: 0
Accepted
time: 3ms
memory: 3656kb

input:

344 4

output:

864324256

result:

ok single line: '864324256'

Test #25:

score: 0
Accepted
time: 0ms
memory: 3644kb

input:

127 3

output:

306783420

result:

ok single line: '306783420'

Test #26:

score: 0
Accepted
time: 0ms
memory: 3720kb

input:

170 4

output:

138463737

result:

ok single line: '138463737'

Test #27:

score: 0
Accepted
time: 0ms
memory: 3628kb

input:

199 3

output:

988988696

result:

ok single line: '988988696'

Test #28:

score: 0
Accepted
time: 0ms
memory: 3724kb

input:

206 3

output:

992080398

result:

ok single line: '992080398'

Test #29:

score: 0
Accepted
time: 0ms
memory: 3580kb

input:

82 2

output:

755922348

result:

ok single line: '755922348'

Test #30:

score: 0
Accepted
time: 0ms
memory: 3604kb

input:

351 2

output:

285073312

result:

ok single line: '285073312'

Test #31:

score: 0
Accepted
time: 0ms
memory: 3664kb

input:

274 1

output:

609866862

result:

ok single line: '609866862'

Test #32:

score: 0
Accepted
time: 0ms
memory: 3612kb

input:

416 3

output:

49398792

result:

ok single line: '49398792'

Test #33:

score: 0
Accepted
time: 0ms
memory: 3624kb

input:

4 2

output:

2

result:

ok single line: '2'

Test #34:

score: 0
Accepted
time: 0ms
memory: 3548kb

input:

5 2

output:

4

result:

ok single line: '4'

Test #35:

score: 0
Accepted
time: 0ms
memory: 3688kb

input:

6 2

output:

7

result:

ok single line: '7'

Test #36:

score: 0
Accepted
time: 0ms
memory: 3680kb

input:

500 2

output:

255888452

result:

ok single line: '255888452'

Test #37:

score: 0
Accepted
time: 0ms
memory: 3628kb

input:

8 3

output:

8

result:

ok single line: '8'

Test #38:

score: 0
Accepted
time: 0ms
memory: 3708kb

input:

9 3

output:

15

result:

ok single line: '15'