QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#419365 | #1423. Bin | grass8cow# | AC ✓ | 4748ms | 48876kb | C++17 | 2.0kb | 2024-05-23 20:58:34 | 2024-05-23 20:58:36 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int mod=998244353,G=3,GI=(mod+1)/3,inv2=(mod+1)/2;
int qpow(int a,int b){
int c=1;
for(;b;b>>=1){
if(b&1)c=1ll*a*c%mod;
a=1ll*a*a%mod;
}
return c;
}
int L,lb[1<<21];
void init(int n){
L=1;while(L<=n)L<<=1;
for(int i=1;i<L;i++)lb[i]=(lb[i>>1]>>1)|((i&1)?(L>>1):0);
}
int wi[1<<21][2];
void NTT(int *a,int fl){
for(int i=0;i<L;i++)if(i<lb[i])swap(a[i],a[lb[i]]);
for(int o=1;o<L;o<<=1){
for(int i=0;i<L;i+=(o<<1))for(int j=0;j<o;j++){
int x=a[i+j],y=1ll*a[i+j+o]*wi[j+o][fl]%mod;
a[i+j]=x+y;if(a[i+j]>=mod)a[i+j]-=mod;
a[i+j+o]=x+mod-y;if(a[i+j+o]>=mod)a[i+j+o]-=mod;
}
}
if(!fl){
int I=qpow(L,mod-2);
for(int i=0;i<L;i++)a[i]=1ll*a[i]*I%mod;
}
}
int n,m,f[1010000];
int p[1<<21],q[1<<21];
void ad(int &x,int y){x+=y;if(x>=mod)x-=mod;}
void cdq(int l,int r){
if(l==r){
if(l==1)return;
if(!(l&1))
(f[l]+=1ll*f[l/2]*f[l/2]%mod)%=mod;
f[l]=1ll*f[l]*inv2%mod;
for(int j=l/2+1;j<=(l+m)/2&&j<l;j++)
(f[l]+=1ll*f[j]*f[l-j]%mod)%=mod;
return;
//2j>i,2j<=i+m
}
int mi=(l+r)>>1;cdq(l,mi);init(r-l+mi-l+1);
for(int i=0;i<L;i++)p[i]=q[i]=0;
for(int i=l;i<=mi;i++)p[i-l]=f[i];
for(int i=1;i<=mi&&i<=r-l;i++)q[i]=f[i];
NTT(p,1),NTT(q,1);for(int i=0;i<L;i++)p[i]=1ll*p[i]*q[i]%mod;
NTT(p,0);
for(int i=mi+1;i<=r;i++)ad(f[i],p[i-l]);
//---
for(int i=0;i<L;i++)p[i]=q[i]=0;
for(int i=l;i<=mi;i++)p[i-l]=f[i];
for(int i=1;i<l&&i<=r-l;i++)q[i]=f[i];
NTT(p,1),NTT(q,1);for(int i=0;i<L;i++)p[i]=1ll*p[i]*q[i]%mod;
NTT(p,0);
for(int i=mi+1;i<=r;i++)ad(f[i],p[i-l]);
cdq(mi+1,r);
}
int main(){
for(int fl=0;fl<2;fl++)for(int o=1;o<(1<<21);o<<=1){
int Wn=qpow(fl?G:GI,(mod-1)/(o<<1)),w=1;
for(int i=0;i<o;i++,w=1ll*w*Wn%mod)wi[i+o][fl]=w;
}
scanf("%d%d",&n,&m);f[1]=1;
cdq(1,n);
printf("%d",f[n]);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 22ms
memory: 26508kb
input:
2 0
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 15ms
memory: 26512kb
input:
3 0
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: 0
Accepted
time: 18ms
memory: 26440kb
input:
3 1
output:
2
result:
ok 1 number(s): "2"
Test #4:
score: 0
Accepted
time: 15ms
memory: 26320kb
input:
4 0
output:
2
result:
ok 1 number(s): "2"
Test #5:
score: 0
Accepted
time: 15ms
memory: 26376kb
input:
4 1
output:
3
result:
ok 1 number(s): "3"
Test #6:
score: 0
Accepted
time: 18ms
memory: 26508kb
input:
4 2
output:
5
result:
ok 1 number(s): "5"
Test #7:
score: 0
Accepted
time: 15ms
memory: 26500kb
input:
6 2
output:
23
result:
ok 1 number(s): "23"
Test #8:
score: 0
Accepted
time: 22ms
memory: 26324kb
input:
7 42
output:
132
result:
ok 1 number(s): "132"
Test #9:
score: 0
Accepted
time: 22ms
memory: 26476kb
input:
10 1
output:
400
result:
ok 1 number(s): "400"
Test #10:
score: 0
Accepted
time: 22ms
memory: 26436kb
input:
13 4
output:
42003
result:
ok 1 number(s): "42003"
Test #11:
score: 0
Accepted
time: 18ms
memory: 26440kb
input:
239 17
output:
385818773
result:
ok 1 number(s): "385818773"
Test #12:
score: 0
Accepted
time: 199ms
memory: 26956kb
input:
50216 58
output:
744498776
result:
ok 1 number(s): "744498776"
Test #13:
score: 0
Accepted
time: 4748ms
memory: 48748kb
input:
787788 78
output:
394429402
result:
ok 1 number(s): "394429402"
Test #14:
score: 0
Accepted
time: 15ms
memory: 26404kb
input:
5 92
output:
14
result:
ok 1 number(s): "14"
Test #15:
score: 0
Accepted
time: 22ms
memory: 26376kb
input:
88 79
output:
931161641
result:
ok 1 number(s): "931161641"
Test #16:
score: 0
Accepted
time: 24ms
memory: 26416kb
input:
749 77
output:
615055472
result:
ok 1 number(s): "615055472"
Test #17:
score: 0
Accepted
time: 26ms
memory: 26524kb
input:
2281 89
output:
282226588
result:
ok 1 number(s): "282226588"
Test #18:
score: 0
Accepted
time: 34ms
memory: 26524kb
input:
5765 35
output:
293680396
result:
ok 1 number(s): "293680396"
Test #19:
score: 0
Accepted
time: 112ms
memory: 26756kb
input:
43189 12
output:
805295564
result:
ok 1 number(s): "805295564"
Test #20:
score: 0
Accepted
time: 4416ms
memory: 48816kb
input:
806855 5
output:
593114139
result:
ok 1 number(s): "593114139"
Test #21:
score: 0
Accepted
time: 4575ms
memory: 48836kb
input:
994514 45
output:
678426421
result:
ok 1 number(s): "678426421"
Test #22:
score: 0
Accepted
time: 4561ms
memory: 48696kb
input:
999921 62
output:
752162081
result:
ok 1 number(s): "752162081"
Test #23:
score: 0
Accepted
time: 4611ms
memory: 48876kb
input:
995033 94
output:
130314865
result:
ok 1 number(s): "130314865"
Test #24:
score: 0
Accepted
time: 4534ms
memory: 48872kb
input:
901438 97
output:
809128292
result:
ok 1 number(s): "809128292"
Test #25:
score: 0
Accepted
time: 4554ms
memory: 48780kb
input:
993020 0
output:
926771801
result:
ok 1 number(s): "926771801"
Test #26:
score: 0
Accepted
time: 4629ms
memory: 48836kb
input:
1000000 100
output:
470305140
result:
ok 1 number(s): "470305140"