QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#22948 | #2892. 合法序列 | ha114514ha# | AC ✓ | 7ms | 5760kb | C++20 | 3.4kb | 2022-03-11 11:53:44 | 2022-04-30 02:10:06 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string.h>
#include<queue>
#include<vector>
#include<map>
#include<bitset>
#include<set>
#include<cmath>
#include<ctime>
#include<random>
#define vi vector<int>
#define pb push_back
#define fi first
#define se second
#define mp make_pair
#define bc(x) __builtin_popcount(x)
#define re register
#define il inline
#define pii pair<int,int>
#define pil pair<int,long long>
#define pll pair<long long,long long>
#define mem0(x) memset(x,0,sizeof(x))
#define mem0x3f(x) memset(x,0x3f,sizeof(x))
#define dbg(x) cerr<<"In Line "<< __LINE__<<" the "<<#x<<" = "<<x<<'\n';
#define dpi(x,y) cerr<<"In Line "<<__LINE__<<" the "<<#x<<" = "<<x<<" ; "<<"the "<<#y<<" = "<<y<<'\n';
// #pragma GCC optimize(3)
//#define int long long
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
namespace IO_BUFF{
mt19937 rnd(time(0)^(ll)(new char));
int rend(int x){
return rnd()%x+1;
}
void rendom_shuffle(int *a,int len){
shuffle(a+1,a+len+1,rnd);
}
const int BS=(1<<24)+5;char Buffer[BS],*HD,*TL;
inline int gc(){
if(HD==TL) TL=(HD=Buffer)+fread(Buffer,1,BS,stdin);
return (HD==TL)?EOF:*HD++;
}
inline int inn(){
int x,ch,s=1;while((ch=gc())<'0'||ch>'9')if(ch=='-')s=-1;x=ch^'0';
while((ch=gc())>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^'0');return x*s;
}
char ssss[19999999],tttt[20];int ssl,ttl;
inline int print(int x)
{
if(x<0)ssss[++ssl]='-',x=(-x);
if(!x) ssss[++ssl]='0';for(ttl=0;x;x/=10) tttt[++ttl]=char(x%10+'0');
for(;ttl;ttl--) ssss[++ssl]=tttt[ttl];return ssss[++ssl]='\n';
}
inline int Flush(){return fwrite(ssss+1,sizeof(char),ssl,stdout),ssl=0,0;}
int read(){
char c=getchar();int x=1;int s=0;
while(c<'0' || c>'9'){if(c=='-')x=-1;c=getchar();}
while(c>='0' && c<='9'){
s=s*10+c-'0';c=getchar();
}
return s*x;
}
}using namespace IO_BUFF;
namespace CFConTest{
const int mod=998244353;
inline int add(const int &x,const int &y){
return (x+y>=mod?x+y-mod:x+y);
}
inline int del(const int &x,const int &y){
return (x-y<0?x-y+mod:x-y);
}
int ksm(int x,int k){
int base=1;
while(k){
if(k&1)base=1ll*base*x%mod;
k>>=1;
x=1ll*x*x%mod;
}
return base;
}
};
using namespace CFConTest;
const int N=505;
int n,m,len;
int f[N][17];
bool check(int u,int x){
if(u&(1<<(x-1)))return 1;
return 0;
}
bool check(int x){
for(int i=1;i<=len-m+1;i++){
int tmp=0;
for(int k=i;k<=i+m-1;k++){
tmp<<=1;
if(x&(1<<(k-1)))tmp|=1;
}
if(!check(x,tmp+1))return 0;
}
return 1;
}
int main(){
#ifdef newbiewzs
freopen("data.in","r",stdin);
#else
#endif
n=read();m=read();
len=(1<<m);
int ans=0;
for(int i=0;i<(1<<len);i++){
if(check(i)){
int x=0;
for(int k=len-m+1;k<=len;k++){
x=x<<=1;
if(i&(1<<(k-1)))x|=1;
}
f[len-m+1][x]=1;
for(int k=len-m+1;k<=n-m+1;k++){
for(int j=0;j<len;j++){
if(!f[k][j])continue;
int tmp=j;
tmp=tmp<<1;
tmp&=((1<<(m))-1);
if(check(i,tmp+1))f[k+1][tmp]=add(f[k+1][tmp],f[k][j]);
if(check(i,(tmp|1)+1))f[k+1][tmp|1]=add(f[k+1][tmp|1],f[k][j]);
}
}
for(int j=0;j<len;j++)ans=add(ans,f[n-m+1][j]);
memset(f,0,sizeof(f));
}
}
cout<<ans;
#ifdef newbiewzs
cerr<<'\n'<<"Time:"<<clock()<<" ms"<<'\n';
#endif
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3692kb
input:
2 1
output:
1
result:
ok single line: '1'
Test #2:
score: 0
Accepted
time: 3ms
memory: 3604kb
input:
10 3
output:
27
result:
ok single line: '27'
Test #3:
score: 0
Accepted
time: 3ms
memory: 3632kb
input:
11 3
output:
46
result:
ok single line: '46'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3492kb
input:
500 3
output:
402086823
result:
ok single line: '402086823'
Test #5:
score: 0
Accepted
time: 4ms
memory: 3720kb
input:
16 4
output:
268
result:
ok single line: '268'
Test #6:
score: 0
Accepted
time: 0ms
memory: 5760kb
input:
17 4
output:
520
result:
ok single line: '520'
Test #7:
score: 0
Accepted
time: 4ms
memory: 3612kb
input:
18 4
output:
939
result:
ok single line: '939'
Test #8:
score: 0
Accepted
time: 4ms
memory: 3696kb
input:
19 4
output:
1634
result:
ok single line: '1634'
Test #9:
score: 0
Accepted
time: 1ms
memory: 3720kb
input:
20 4
output:
2678
result:
ok single line: '2678'
Test #10:
score: 0
Accepted
time: 2ms
memory: 3584kb
input:
500 4
output:
905810545
result:
ok single line: '905810545'
Test #11:
score: 0
Accepted
time: 4ms
memory: 3576kb
input:
156 3
output:
158348364
result:
ok single line: '158348364'
Test #12:
score: 0
Accepted
time: 4ms
memory: 3608kb
input:
3 1
output:
2
result:
ok single line: '2'
Test #13:
score: 0
Accepted
time: 3ms
memory: 3628kb
input:
419 1
output:
309520444
result:
ok single line: '309520444'
Test #14:
score: 0
Accepted
time: 3ms
memory: 3632kb
input:
148 1
output:
981388471
result:
ok single line: '981388471'
Test #15:
score: 0
Accepted
time: 3ms
memory: 3612kb
input:
208 1
output:
17788609
result:
ok single line: '17788609'
Test #16:
score: 0
Accepted
time: 3ms
memory: 3560kb
input:
325 4
output:
534470501
result:
ok single line: '534470501'
Test #17:
score: 0
Accepted
time: 1ms
memory: 3564kb
input:
478 1
output:
275981743
result:
ok single line: '275981743'
Test #18:
score: 0
Accepted
time: 1ms
memory: 3720kb
input:
437 3
output:
448979837
result:
ok single line: '448979837'
Test #19:
score: 0
Accepted
time: 0ms
memory: 3724kb
input:
260 3
output:
249722589
result:
ok single line: '249722589'
Test #20:
score: 0
Accepted
time: 1ms
memory: 3612kb
input:
406 2
output:
762498912
result:
ok single line: '762498912'
Test #21:
score: 0
Accepted
time: 3ms
memory: 3632kb
input:
348 2
output:
718553190
result:
ok single line: '718553190'
Test #22:
score: 0
Accepted
time: 3ms
memory: 3608kb
input:
350 1
output:
496751081
result:
ok single line: '496751081'
Test #23:
score: 0
Accepted
time: 3ms
memory: 3632kb
input:
500 1
output:
154029661
result:
ok single line: '154029661'
Test #24:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
344 4
output:
864324256
result:
ok single line: '864324256'
Test #25:
score: 0
Accepted
time: 1ms
memory: 3696kb
input:
127 3
output:
306783420
result:
ok single line: '306783420'
Test #26:
score: 0
Accepted
time: 7ms
memory: 3628kb
input:
170 4
output:
138463737
result:
ok single line: '138463737'
Test #27:
score: 0
Accepted
time: 3ms
memory: 3696kb
input:
199 3
output:
988988696
result:
ok single line: '988988696'
Test #28:
score: 0
Accepted
time: 3ms
memory: 3600kb
input:
206 3
output:
992080398
result:
ok single line: '992080398'
Test #29:
score: 0
Accepted
time: 3ms
memory: 3580kb
input:
82 2
output:
755922348
result:
ok single line: '755922348'
Test #30:
score: 0
Accepted
time: 1ms
memory: 3764kb
input:
351 2
output:
285073312
result:
ok single line: '285073312'
Test #31:
score: 0
Accepted
time: 3ms
memory: 3692kb
input:
274 1
output:
609866862
result:
ok single line: '609866862'
Test #32:
score: 0
Accepted
time: 1ms
memory: 3608kb
input:
416 3
output:
49398792
result:
ok single line: '49398792'
Test #33:
score: 0
Accepted
time: 3ms
memory: 3496kb
input:
4 2
output:
2
result:
ok single line: '2'
Test #34:
score: 0
Accepted
time: 4ms
memory: 3580kb
input:
5 2
output:
4
result:
ok single line: '4'
Test #35:
score: 0
Accepted
time: 2ms
memory: 3636kb
input:
6 2
output:
7
result:
ok single line: '7'
Test #36:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
500 2
output:
255888452
result:
ok single line: '255888452'
Test #37:
score: 0
Accepted
time: 3ms
memory: 3608kb
input:
8 3
output:
8
result:
ok single line: '8'
Test #38:
score: 0
Accepted
time: 3ms
memory: 3612kb
input:
9 3
output:
15
result:
ok single line: '15'