QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#622704 | #1423. Bin | Afterlife | AC ✓ | 3400ms | 39588kb | C++20 | 4.3kb | 2024-10-09 00:26:33 | 2024-10-09 00:26:34 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=998244353;
inline int inc(int x,int y){return x+y>=mod?x+y-mod:x+y;}
inline int dec(int x,int y){return x-y<0?x-y+mod:x-y;}
inline int mul(int x,int y){return (ll)x*y%mod;}
inline int qpow(int x,int y){
int res=1;
for(;y;y>>=1)res=y&1?mul(res,x):res,x=mul(x,x);
return res;
}
inline int inv(int x){return qpow(x,mod-2);}
const int N=1<<20;
namespace NTT{
int re[N],w[2][N];
inline int getre(int n){
int len=1,bit=0;
while(len<n)len<<=1,++bit;
for(int i=1;i<len;++i)re[i]=(re[i>>1]>>1)|((i&1)<<(bit-1));
w[0][0]=w[1][0]=1,w[0][1]=qpow(3,(mod-1)/len),w[1][1]=inv(w[0][1]);
for(int o=0;o<2;++o)for(int i=2;i<len;++i)
w[o][i]=mul(w[o][i-1],w[o][1]);
return len;
}
inline void NTT(int* a,int n,int o=0){
for(int i=1;i<n;++i)if(i<re[i])swap(a[i],a[re[i]]);
int R;
for(int k=1;k<n;k<<=1)
for(int i=0,t=k<<1,st=n/t;i<n;i+=t)
for(int j=0,nw=0;j<k;++j,nw+=st)
R=mul(a[i+j+k],w[o][nw]),a[i+j+k]=dec(a[i+j],R),a[i+j]=inc(a[i+j],R);
if(o){
R=inv(n);
for(int i=0;i<n;++i)a[i]=mul(a[i],R);
}
}
int t0[N],t1[N],t2[N];
inline void multi(const int* a,const int* b,int* c,int n,int m){
if(n+m<=32){
memset(c,0,sizeof(int)*(n+m+1));
for(int i=0;i<=n;++i)
for(int j=0;j<=m;++j)
c[i+j]=inc(c[i+j],mul(a[i],b[j]));
return;
}
int len=getre(n+m+1);
memset(t0,0,sizeof(int)*len),memcpy(t0,a,sizeof(int)*(n+1));
memset(t1,0,sizeof(int)*len),memcpy(t1,b,sizeof(int)*(m+1));
NTT(t0,len),NTT(t1,len);
for(int i=0;i<len;++i)t0[i]=mul(t0[i],t1[i]);
NTT(t0,len,1);
memcpy(c,t0,sizeof(int)*(n+m+1));
}
inline void inver(const int* a,int* b,int n){
int len=1;
while(len<=n)len<<=1;
memset(t0,0,sizeof(int)*len),memcpy(t0,a,sizeof(int)*(n+1));
memset(t1,0,sizeof(int)*(len<<1));
memset(t2,0,sizeof(int)*(len<<1));
t2[0]=inv(t0[0]);
for(int k=1;k<=len;k<<=1){
memcpy(t1,t0,sizeof(int)*k);
getre(k<<1);
NTT(t1,k<<1),NTT(t2,k<<1);
for(int i=0;i<(k<<1);++i)t2[i]=mul(t2[i],dec(2,mul(t1[i],t2[i])));
NTT(t2,k<<1,1);
for(int i=k;i<(k<<1);++i)t2[i]=0;
}
memcpy(b,t2,sizeof(int)*(n+1));
}
} //namespace NTT
struct poly:public vector<int>{
inline int time()const{return size()-1;}
inline poly(int tim=0,int c=0){
resize(tim+1);
if(tim>=0)at(0)=c;
}
inline poly(int *l,int *r) {
resize((r-l)+1);
for(int i = 0;i < size();i++) at(i) = *(l + i);
}
inline poly operator%(const int& n)const{
poly r(*this);
r.resize(n);
return r;
}
inline poly operator%=(const int& n){
resize(n);
return *this;
}
inline poly operator+(const poly& p)const{
int n=time(),m=p.time();
poly r(*this);
if(n<m)r.resize(m+1);
for(int i=0;i<=m;++i)r[i]=inc(r[i],p[i]);
return r;
}
inline poly operator-(const poly& p)const{
int n=time(),m=p.time();
poly r(*this);
if(n<m)r.resize(m+1);
for(int i=0;i<=m;++i)r[i]=dec(r[i],p[i]);
return r;
}
inline poly operator*(const poly& p)const{
poly r(time()+p.time());
NTT::multi(&((*this)[0]),&p[0],&r[0],time(),p.time());
return r;
}
inline poly operator*(const int& k)const{
poly r(*this);
int n=time();
for(int i=0;i<=n;++i)r[i]=mul(r[i],k);
return r;
}
inline poly operator~()const{
poly r(*this);
reverse(r.begin(),r.end());
return r;
}
};
int f[1000005];
int n , k;
void solve(int l,int r) {
if(l == r) {
for(int i = (l + 1) / 2 ; i <= (l - i) + k && i < l; i++) {
f[l] = (f[l] + 1LL * f[i] * f[l - i]) % mod;
}
// printf("%d %d\n",l,f[l]) ;
return ;
}
int md = (l + r >> 1);
solve(l , md);
if(l != 1) {
poly a(f + l , f + md) ;
poly b(f + 1 , f + r - l) ;
a = a * b;
for(int i = md + 1 ; i <= r;i++) {
f[i] = (f[i] + a[i - (l + 1)]) % mod;
}
}
solve(md + 1 , r) ;
poly a(f + l , f+md);
poly b(f + md + 1 , f + r) ;
a = a * b;
for(int i = 0;i < a.size() && i + md + 1 <= n;i++) {
// printf("on %d %d : %d %d: contri %d\n",l,md,md+1,r,i+l+md+1);
if(i + l + md + 1 > r)
f[i + l + md + 1] = (f[i + l + md + 1] + a[i]) % mod;
}
return ;
}
int main() {
cin >> n >> k;
f[1] = 1;
solve(1 , n );
cout << f[n] << '\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3624kb
input:
2 0
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
3 0
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3680kb
input:
3 1
output:
2
result:
ok 1 number(s): "2"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3688kb
input:
4 0
output:
2
result:
ok 1 number(s): "2"
Test #5:
score: 0
Accepted
time: 1ms
memory: 3656kb
input:
4 1
output:
3
result:
ok 1 number(s): "3"
Test #6:
score: 0
Accepted
time: 1ms
memory: 3920kb
input:
4 2
output:
5
result:
ok 1 number(s): "5"
Test #7:
score: 0
Accepted
time: 1ms
memory: 3508kb
input:
6 2
output:
23
result:
ok 1 number(s): "23"
Test #8:
score: 0
Accepted
time: 0ms
memory: 3656kb
input:
7 42
output:
132
result:
ok 1 number(s): "132"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3688kb
input:
10 1
output:
400
result:
ok 1 number(s): "400"
Test #10:
score: 0
Accepted
time: 1ms
memory: 3924kb
input:
13 4
output:
42003
result:
ok 1 number(s): "42003"
Test #11:
score: 0
Accepted
time: 2ms
memory: 11924kb
input:
239 17
output:
385818773
result:
ok 1 number(s): "385818773"
Test #12:
score: 0
Accepted
time: 120ms
memory: 12728kb
input:
50216 58
output:
744498776
result:
ok 1 number(s): "744498776"
Test #13:
score: 0
Accepted
time: 3225ms
memory: 36600kb
input:
787788 78
output:
394429402
result:
ok 1 number(s): "394429402"
Test #14:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
5 92
output:
14
result:
ok 1 number(s): "14"
Test #15:
score: 0
Accepted
time: 0ms
memory: 12048kb
input:
88 79
output:
931161641
result:
ok 1 number(s): "931161641"
Test #16:
score: 0
Accepted
time: 0ms
memory: 11724kb
input:
749 77
output:
615055472
result:
ok 1 number(s): "615055472"
Test #17:
score: 0
Accepted
time: 3ms
memory: 11760kb
input:
2281 89
output:
282226588
result:
ok 1 number(s): "282226588"
Test #18:
score: 0
Accepted
time: 8ms
memory: 12204kb
input:
5765 35
output:
293680396
result:
ok 1 number(s): "293680396"
Test #19:
score: 0
Accepted
time: 76ms
memory: 12544kb
input:
43189 12
output:
805295564
result:
ok 1 number(s): "805295564"
Test #20:
score: 0
Accepted
time: 3141ms
memory: 36736kb
input:
806855 5
output:
593114139
result:
ok 1 number(s): "593114139"
Test #21:
score: 0
Accepted
time: 3268ms
memory: 39372kb
input:
994514 45
output:
678426421
result:
ok 1 number(s): "678426421"
Test #22:
score: 0
Accepted
time: 3301ms
memory: 39588kb
input:
999921 62
output:
752162081
result:
ok 1 number(s): "752162081"
Test #23:
score: 0
Accepted
time: 3349ms
memory: 39256kb
input:
995033 94
output:
130314865
result:
ok 1 number(s): "130314865"
Test #24:
score: 0
Accepted
time: 3334ms
memory: 38900kb
input:
901438 97
output:
809128292
result:
ok 1 number(s): "809128292"
Test #25:
score: 0
Accepted
time: 3198ms
memory: 39492kb
input:
993020 0
output:
926771801
result:
ok 1 number(s): "926771801"
Test #26:
score: 0
Accepted
time: 3400ms
memory: 39572kb
input:
1000000 100
output:
470305140
result:
ok 1 number(s): "470305140"