QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#66064 | #1423. Bin | eyiigjkn | AC ✓ | 2130ms | 31908kb | C++14 | 2.2kb | 2022-12-06 10:08:28 | 2022-12-06 10:08:28 |
Judging History
answer
# include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ull=unsigned long long;
constexpr int mod=998244353,g=3,_2=499122177;
int K,maxn,rev[2100000],pwg[2100000],f[1000010],F[2100000],G[2100000];
inline int add(int x,int y){return (x+=y)<mod?x:x-mod;}
inline void upd(int &x,const int &y){if((x+=y)>=mod) x-=mod;}
inline void upd(int &x,const ll &y){x=(x+y)%mod;}
int power(int a,int b)
{
int ans=1;
for(;b;b>>=1,a=(ll)a*a%mod)
if(b&1) ans=(ll)ans*a%mod;
return ans;
}
void init(int n)
{
int l=0;
for(maxn=1;maxn<n;maxn<<=1) l++;
for(int i=1;i<maxn;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<l-1);
for(int i=1;i<maxn;i<<=1)
{
int wm=power(g,(mod-1)/(i<<1));
pwg[i]=1;
for(int j=1;j<i;j++) pwg[i+j]=(ll)pwg[i+j-1]*wm%mod;
}
}
void NTT(int *p,bool flag)
{
static ull a[2100000];
for(int i=0;i<maxn;i++) a[i]=p[rev[i]];
for(int i=1;i<maxn;i<<=1)
{
for(int j=0;j<maxn;j+=i<<1)
for(int k=j;k<j+i;k++)
{
ull x=a[k],y=a[k+i]*pwg[i-j+k]%mod;
a[k]=x+y;a[k+i]=x-y+mod;
}
if(i==1024) for(int j=0;j<maxn;j++) a[j]%=mod;
}
for(int i=0;i<maxn;i++) p[i]=a[i]%mod;
if(flag) return;
int invn=power(maxn,mod-2);
reverse(p+1,p+maxn);
for(int i=0;i<maxn;i++) p[i]=(ll)p[i]*invn%mod;
}
void slv(int l,int r)
{
if(l==r)
{
if(l==0) return f[l]=0,void();
else if(l==1) return f[l]=1,void();
if(~l&1) upd(f[l],(ll)f[l/2]*f[l/2]);
f[l]=(ll)f[l]*_2%mod;
for(int i=l/2+1;i<l && i-(l-i)<=K;i++) upd(f[l],(ll)f[i]*f[l-i]);
return;
}
int mid=(l+r)/2;
slv(l,mid);
if(l)
{
for(int i=l;i<=mid;i++) F[i-l]=f[i];
for(int i=0;i<=r-l;i++) G[i]=f[i];
init(mid-l+r-l+1);
NTT(F,1);NTT(G,1);
for(int i=0;i<maxn;i++) F[i]=2ll*F[i]*G[i]%mod;
NTT(F,0);
for(int i=mid+1;i<=r;i++) upd(f[i],F[i-l]);
memset(F,0,sizeof(int)*maxn);
memset(G,0,sizeof(int)*maxn);
}
else
{
for(int i=l;i<=mid;i++) F[i]=f[i];
init(2*mid+1);
NTT(F,1);
for(int i=0;i<maxn;i++) F[i]=(ll)F[i]*F[i]%mod;
NTT(F,0);
for(int i=mid+1;i<=r;i++) upd(f[i],F[i]);
memset(F,0,sizeof(int)*maxn);
}
slv(mid+1,r);
}
int main()
{
int n;
cin>>n>>K;
slv(0,n);
cout<<f[n]<<endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3400kb
input:
2 0
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 2ms
memory: 3296kb
input:
3 0
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: 0
Accepted
time: 2ms
memory: 3284kb
input:
3 1
output:
2
result:
ok 1 number(s): "2"
Test #4:
score: 0
Accepted
time: 2ms
memory: 3296kb
input:
4 0
output:
2
result:
ok 1 number(s): "2"
Test #5:
score: 0
Accepted
time: 2ms
memory: 3284kb
input:
4 1
output:
3
result:
ok 1 number(s): "3"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3288kb
input:
4 2
output:
5
result:
ok 1 number(s): "5"
Test #7:
score: 0
Accepted
time: 2ms
memory: 3332kb
input:
6 2
output:
23
result:
ok 1 number(s): "23"
Test #8:
score: 0
Accepted
time: 1ms
memory: 3432kb
input:
7 42
output:
132
result:
ok 1 number(s): "132"
Test #9:
score: 0
Accepted
time: 2ms
memory: 3236kb
input:
10 1
output:
400
result:
ok 1 number(s): "400"
Test #10:
score: 0
Accepted
time: 0ms
memory: 3236kb
input:
13 4
output:
42003
result:
ok 1 number(s): "42003"
Test #11:
score: 0
Accepted
time: 2ms
memory: 3292kb
input:
239 17
output:
385818773
result:
ok 1 number(s): "385818773"
Test #12:
score: 0
Accepted
time: 88ms
memory: 5064kb
input:
50216 58
output:
744498776
result:
ok 1 number(s): "744498776"
Test #13:
score: 0
Accepted
time: 1920ms
memory: 30948kb
input:
787788 78
output:
394429402
result:
ok 1 number(s): "394429402"
Test #14:
score: 0
Accepted
time: 0ms
memory: 3424kb
input:
5 92
output:
14
result:
ok 1 number(s): "14"
Test #15:
score: 0
Accepted
time: 2ms
memory: 3292kb
input:
88 79
output:
931161641
result:
ok 1 number(s): "931161641"
Test #16:
score: 0
Accepted
time: 3ms
memory: 3316kb
input:
749 77
output:
615055472
result:
ok 1 number(s): "615055472"
Test #17:
score: 0
Accepted
time: 5ms
memory: 3380kb
input:
2281 89
output:
282226588
result:
ok 1 number(s): "282226588"
Test #18:
score: 0
Accepted
time: 10ms
memory: 3616kb
input:
5765 35
output:
293680396
result:
ok 1 number(s): "293680396"
Test #19:
score: 0
Accepted
time: 46ms
memory: 4944kb
input:
43189 12
output:
805295564
result:
ok 1 number(s): "805295564"
Test #20:
score: 0
Accepted
time: 1832ms
memory: 30960kb
input:
806855 5
output:
593114139
result:
ok 1 number(s): "593114139"
Test #21:
score: 0
Accepted
time: 2070ms
memory: 31832kb
input:
994514 45
output:
678426421
result:
ok 1 number(s): "678426421"
Test #22:
score: 0
Accepted
time: 2076ms
memory: 31824kb
input:
999921 62
output:
752162081
result:
ok 1 number(s): "752162081"
Test #23:
score: 0
Accepted
time: 2125ms
memory: 31824kb
input:
995033 94
output:
130314865
result:
ok 1 number(s): "130314865"
Test #24:
score: 0
Accepted
time: 2075ms
memory: 31460kb
input:
901438 97
output:
809128292
result:
ok 1 number(s): "809128292"
Test #25:
score: 0
Accepted
time: 1968ms
memory: 31856kb
input:
993020 0
output:
926771801
result:
ok 1 number(s): "926771801"
Test #26:
score: 0
Accepted
time: 2130ms
memory: 31908kb
input:
1000000 100
output:
470305140
result:
ok 1 number(s): "470305140"