QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#83708 | #2892. 合法序列 | fengyuyue# | AC ✓ | 5ms | 3532kb | C++14 | 3.5kb | 2023-03-03 11:05:10 | 2023-03-03 11:05:12 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define fi first
#define se second
#define mkp make_pair
#define pb push_back
#define gc getchar
#define pc putchar
#define pii pair<int,int>
#define pil pair<int,long long>
#define pli pair<long long,int>
#define pll pair<long long,long long>
#define For(i,l,r) for(int i=(l);i<=(r);i++)
#define IFor(i,r,l) for(int i=(r);i>=(l);i--)
#define for_son(u) for(int e=head[u];e;e=nxt[e])
#define eps (1e-8)
#define INF 0x3f3f3f3f
using namespace std;
char aa;
namespace ljh
{
namespace IO
{
// const int SIZ=1<<20;
// char ibuf[SIZ],*p1,*p2,obuf[SIZ],*p3=obuf;
// #define gc() (p1==p2&&(p2=(p1=ibuf)+fread(ibuf,1,SIZ,stdin),p1==p2)?EOF:*p1++)
// void pc(const char &c)
// {
// if(p3-obuf==SIZ) fwrite(obuf,1,SIZ,stdout),p3=obuf;
// *p3++=c;
// }
int rd()
{
int x=0,f=1;
char ch=gc();
while(!isdigit(ch)){
if(ch=='-') f=-1;
ch=gc();
}
while(isdigit(ch)){
x=x*10+ch-'0';
ch=gc();
}
return x*f;
}
void wr(int x,char ch)
{
if(x<0) x=-x,pc('-');
static char st[12];
int top=0;
do{
st[top++]=x%10+'0',x/=10;
}while(x);
while(top) pc(st[--top]);
pc(ch);
}
ll ll_rd()
{
ll x=0;
int f=1;
char ch=gc();
while(!isdigit(ch)){
if(ch=='-') f=-1;
ch=gc();
}
while(isdigit(ch)){
x=x*10+ch-'0';
ch=gc();
}
return x*f;
}
void ll_wr(ll x,char ch)
{
if(x<0) x=-x,pc('-');
static char st[22];
int top=0;
do{
st[top++]=x%10+'0',x/=10;
}while(x);
while(top) pc(st[--top]);
pc(ch);
}
}
using namespace IO;
const int N=505,mod=998244353;
namespace tem
{
// void add_edge(int u,int v){nxt[++cnt]=head[u],to[cnt]=v,head[u]=cnt;}
int qpow(int a,int b,int p)
{
a%=p;
int res=1;
while(b){
if(b&1) res=1ll*res*a%p;
a=1ll*a*a%p;
b>>=1;
}
return res;
}
int get_inv(int x){return qpow(x,mod-2,mod);}
int lowbit(int x){return x&(-x);}
void add(int &x,const int y){ x=(x+y>=mod?x+y-mod:x+y); }
// int get(int x) {return fa[x]==x?x:fa[x]=get(fa[x])};
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a,b)*b;}
}
using namespace tem;
int n,k,f[N][8],ans,l,U;
bool bit(int s,int i)
{
return s>>(l-1-i)&1;
}
void main()
{
n=rd(),k=rd();
l=1<<k,U=(1<<k)-1;
For(s,0,(1<<l)-1){
bool flag=true;
For(i,0,l-k){
if(!bit(s,(s&(U<<i))>>i)){
flag=false;
break;
}
}
if(!flag) continue;
// cerr<<s<<endl;
memset(f,0,sizeof(f));
f[0][s&(U>>1)]=1;
For(i,0,n-l-1){
For(j,0,U>>1){
int x=f[i][j];
if(!x) continue;
if(bit(s,j<<1)) add(f[i+1][(j<<1)&(U>>1)],x);
if(bit(s,j<<1|1)) add(f[i+1][(j<<1|1)&(U>>1)],x);
}
}
For(i,0,U>>1){
add(ans,f[n-l][i]);
}
}
wr(ans,'\n');
// fwrite(obuf,1,p3-obuf,stdout);
}
/*
*/
}
char bb;
int main()
{
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
// int st=clock();
ljh::main();
// int ed=clock();
// cerr<<ed-st<<"ms"<<endl;
// cerr<<(&bb-&aa)/1024/1024<<"MB"<<endl;
// fclose(stdin);
// fclose(stdout);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3464kb
input:
2 1
output:
1
result:
ok single line: '1'
Test #2:
score: 0
Accepted
time: 2ms
memory: 3364kb
input:
10 3
output:
27
result:
ok single line: '27'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3348kb
input:
11 3
output:
46
result:
ok single line: '46'
Test #4:
score: 0
Accepted
time: 1ms
memory: 3504kb
input:
500 3
output:
402086823
result:
ok single line: '402086823'
Test #5:
score: 0
Accepted
time: 1ms
memory: 3396kb
input:
16 4
output:
268
result:
ok single line: '268'
Test #6:
score: 0
Accepted
time: 2ms
memory: 3360kb
input:
17 4
output:
520
result:
ok single line: '520'
Test #7:
score: 0
Accepted
time: 1ms
memory: 3384kb
input:
18 4
output:
939
result:
ok single line: '939'
Test #8:
score: 0
Accepted
time: 3ms
memory: 3364kb
input:
19 4
output:
1634
result:
ok single line: '1634'
Test #9:
score: 0
Accepted
time: 2ms
memory: 3396kb
input:
20 4
output:
2678
result:
ok single line: '2678'
Test #10:
score: 0
Accepted
time: 5ms
memory: 3464kb
input:
500 4
output:
905810545
result:
ok single line: '905810545'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3532kb
input:
156 3
output:
158348364
result:
ok single line: '158348364'
Test #12:
score: 0
Accepted
time: 2ms
memory: 3504kb
input:
3 1
output:
2
result:
ok single line: '2'
Test #13:
score: 0
Accepted
time: 2ms
memory: 3372kb
input:
419 1
output:
309520444
result:
ok single line: '309520444'
Test #14:
score: 0
Accepted
time: 2ms
memory: 3376kb
input:
148 1
output:
981388471
result:
ok single line: '981388471'
Test #15:
score: 0
Accepted
time: 2ms
memory: 3344kb
input:
208 1
output:
17788609
result:
ok single line: '17788609'
Test #16:
score: 0
Accepted
time: 2ms
memory: 3468kb
input:
325 4
output:
534470501
result:
ok single line: '534470501'
Test #17:
score: 0
Accepted
time: 2ms
memory: 3372kb
input:
478 1
output:
275981743
result:
ok single line: '275981743'
Test #18:
score: 0
Accepted
time: 1ms
memory: 3400kb
input:
437 3
output:
448979837
result:
ok single line: '448979837'
Test #19:
score: 0
Accepted
time: 2ms
memory: 3372kb
input:
260 3
output:
249722589
result:
ok single line: '249722589'
Test #20:
score: 0
Accepted
time: 1ms
memory: 3528kb
input:
406 2
output:
762498912
result:
ok single line: '762498912'
Test #21:
score: 0
Accepted
time: 0ms
memory: 3372kb
input:
348 2
output:
718553190
result:
ok single line: '718553190'
Test #22:
score: 0
Accepted
time: 2ms
memory: 3532kb
input:
350 1
output:
496751081
result:
ok single line: '496751081'
Test #23:
score: 0
Accepted
time: 1ms
memory: 3352kb
input:
500 1
output:
154029661
result:
ok single line: '154029661'
Test #24:
score: 0
Accepted
time: 2ms
memory: 3372kb
input:
344 4
output:
864324256
result:
ok single line: '864324256'
Test #25:
score: 0
Accepted
time: 2ms
memory: 3524kb
input:
127 3
output:
306783420
result:
ok single line: '306783420'
Test #26:
score: 0
Accepted
time: 1ms
memory: 3360kb
input:
170 4
output:
138463737
result:
ok single line: '138463737'
Test #27:
score: 0
Accepted
time: 0ms
memory: 3376kb
input:
199 3
output:
988988696
result:
ok single line: '988988696'
Test #28:
score: 0
Accepted
time: 1ms
memory: 3380kb
input:
206 3
output:
992080398
result:
ok single line: '992080398'
Test #29:
score: 0
Accepted
time: 2ms
memory: 3508kb
input:
82 2
output:
755922348
result:
ok single line: '755922348'
Test #30:
score: 0
Accepted
time: 0ms
memory: 3468kb
input:
351 2
output:
285073312
result:
ok single line: '285073312'
Test #31:
score: 0
Accepted
time: 2ms
memory: 3532kb
input:
274 1
output:
609866862
result:
ok single line: '609866862'
Test #32:
score: 0
Accepted
time: 2ms
memory: 3344kb
input:
416 3
output:
49398792
result:
ok single line: '49398792'
Test #33:
score: 0
Accepted
time: 2ms
memory: 3344kb
input:
4 2
output:
2
result:
ok single line: '2'
Test #34:
score: 0
Accepted
time: 3ms
memory: 3312kb
input:
5 2
output:
4
result:
ok single line: '4'
Test #35:
score: 0
Accepted
time: 1ms
memory: 3528kb
input:
6 2
output:
7
result:
ok single line: '7'
Test #36:
score: 0
Accepted
time: 2ms
memory: 3340kb
input:
500 2
output:
255888452
result:
ok single line: '255888452'
Test #37:
score: 0
Accepted
time: 2ms
memory: 3364kb
input:
8 3
output:
8
result:
ok single line: '8'
Test #38:
score: 0
Accepted
time: 1ms
memory: 3308kb
input:
9 3
output:
15
result:
ok single line: '15'