QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#831759 | #1423. Bin | hxhhxh | AC ✓ | 3123ms | 53620kb | C++23 | 1.3kb | 2024-12-25 16:41:16 | 2024-12-25 16:41:20 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
#define mod 998244353
using namespace std;
int n,k,f[1000006],a[4100006],b[4100006],c[4100006],r[4100006];
int pw(int x,int p){
int res=1;
for(;p;p>>=1,x=x*x%mod) if(p&1) res=res*x%mod;
return res;
}
void NTT(int*A,int N,int t=1){
for(int i=0,k=__lg(N)-1;i<N;i++) r[i]=(r[i>>1]>>1)|((i&1)<<k);
for(int i=0;i<N;i++) if(i<r[i]) swap(A[i],A[r[i]]);
int nw=(mod-1)/2;
for(int i=1;i<N;i+=i){
int Wn=pw(pw(114514,t),nw);
for(int j=0;j<N;j+=i+i){
int w=1;
for(int k=0;k<i;k++){
int x=A[j+k],y=w*A[j+k+i]%mod;
A[j+k]=(x+y)%mod;
A[j+k+i]=(x-y+mod)%mod;
w=w*Wn%mod;
}
}
nw/=2;
}
if(t>1) for(int i=0,w=pw(N,mod-2);i<N;i++) A[i]=A[i]*w%mod;
}
void slv(int l,int r){
if(l==r){
if(l%2==1) f[l]=(f[l]+f[l/2]*f[l/2])%mod;
f[l]=f[l]*(mod+1)/2%mod;
for(int i=(l+1)/2;i-(l-i-1)<=k&&i<l;i++) f[l]=(f[l]+f[i]*f[l-i-1])%mod;
return;
}
int mid=l+r>>1;
slv(l,mid);
int N=r-l+1;
while((N&-N)<N) N+=N&-N;
for(int i=0;i<N;i++) b[i]=i<=mid?f[i]:0;
for(int i=0;i<N;i++) a[i]=i+l<=mid?f[i+l]:0;
NTT(a,N);
NTT(b,N);
for(int i=0;i<N;i++) c[i]=a[i]*b[i]%mod;
NTT(c,N,mod-2);
for(int i=mid+1;i<=r;i++) f[i]=(f[i]+c[i-1-l]*(1+!!l))%mod;
slv(mid+1,r);
}
signed main(){
cin>>n>>k;
f[0]=2;
slv(0,n-1);
cout<<f[n-1];
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 11820kb
input:
2 0
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 11884kb
input:
3 0
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: 0
Accepted
time: 2ms
memory: 11752kb
input:
3 1
output:
2
result:
ok 1 number(s): "2"
Test #4:
score: 0
Accepted
time: 2ms
memory: 11880kb
input:
4 0
output:
2
result:
ok 1 number(s): "2"
Test #5:
score: 0
Accepted
time: 0ms
memory: 11880kb
input:
4 1
output:
3
result:
ok 1 number(s): "3"
Test #6:
score: 0
Accepted
time: 0ms
memory: 11700kb
input:
4 2
output:
5
result:
ok 1 number(s): "5"
Test #7:
score: 0
Accepted
time: 0ms
memory: 11896kb
input:
6 2
output:
23
result:
ok 1 number(s): "23"
Test #8:
score: 0
Accepted
time: 2ms
memory: 11880kb
input:
7 42
output:
132
result:
ok 1 number(s): "132"
Test #9:
score: 0
Accepted
time: 0ms
memory: 11820kb
input:
10 1
output:
400
result:
ok 1 number(s): "400"
Test #10:
score: 0
Accepted
time: 2ms
memory: 11696kb
input:
13 4
output:
42003
result:
ok 1 number(s): "42003"
Test #11:
score: 0
Accepted
time: 0ms
memory: 11820kb
input:
239 17
output:
385818773
result:
ok 1 number(s): "385818773"
Test #12:
score: 0
Accepted
time: 133ms
memory: 14436kb
input:
50216 58
output:
744498776
result:
ok 1 number(s): "744498776"
Test #13:
score: 0
Accepted
time: 2938ms
memory: 51900kb
input:
787788 78
output:
394429402
result:
ok 1 number(s): "394429402"
Test #14:
score: 0
Accepted
time: 2ms
memory: 11820kb
input:
5 92
output:
14
result:
ok 1 number(s): "14"
Test #15:
score: 0
Accepted
time: 0ms
memory: 11696kb
input:
88 79
output:
931161641
result:
ok 1 number(s): "931161641"
Test #16:
score: 0
Accepted
time: 3ms
memory: 11760kb
input:
749 77
output:
615055472
result:
ok 1 number(s): "615055472"
Test #17:
score: 0
Accepted
time: 2ms
memory: 13860kb
input:
2281 89
output:
282226588
result:
ok 1 number(s): "282226588"
Test #18:
score: 0
Accepted
time: 15ms
memory: 11892kb
input:
5765 35
output:
293680396
result:
ok 1 number(s): "293680396"
Test #19:
score: 0
Accepted
time: 126ms
memory: 12252kb
input:
43189 12
output:
805295564
result:
ok 1 number(s): "805295564"
Test #20:
score: 0
Accepted
time: 2856ms
memory: 52036kb
input:
806855 5
output:
593114139
result:
ok 1 number(s): "593114139"
Test #21:
score: 0
Accepted
time: 3020ms
memory: 51456kb
input:
994514 45
output:
678426421
result:
ok 1 number(s): "678426421"
Test #22:
score: 0
Accepted
time: 3034ms
memory: 53620kb
input:
999921 62
output:
752162081
result:
ok 1 number(s): "752162081"
Test #23:
score: 0
Accepted
time: 3112ms
memory: 51536kb
input:
995033 94
output:
130314865
result:
ok 1 number(s): "130314865"
Test #24:
score: 0
Accepted
time: 3035ms
memory: 52660kb
input:
901438 97
output:
809128292
result:
ok 1 number(s): "809128292"
Test #25:
score: 0
Accepted
time: 2957ms
memory: 53372kb
input:
993020 0
output:
926771801
result:
ok 1 number(s): "926771801"
Test #26:
score: 0
Accepted
time: 3123ms
memory: 51436kb
input:
1000000 100
output:
470305140
result:
ok 1 number(s): "470305140"