QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#400647 | #4903. 细菌 | Dawnq | 40 | 211ms | 23512kb | C++14 | 2.6kb | 2024-04-27 14:38:23 | 2024-04-27 14:38:24 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=6e5+5,mod=998244353,B=5000,G=3,lim=1<<19;
int d,n,m,k,a,b,c;
int dp[2][N],f[N],g[N],h[N],fac[N],inv[N],rev[N],w[N]={1};
inline int Add(int x,int y){return x+y-mod*(x+y>=mod);}
inline int qpow(int x,int y){
int Res=1;while(y){
if(y&1)Res=1ll*Res*x%mod;
x=1ll*x*x%mod,y>>=1;
}return Res;
}
inline int C(int x,int y){return x<0||y<0||x<y?0:1ll*fac[x]*inv[y]%mod*inv[x-y]%mod;}
inline void pre(int n){
fac[0]=1;
for(int i=1;i<=n;++i)fac[i]=1ll*fac[i-1]*i%mod;
inv[n]=qpow(fac[n],mod-2);
for(int i=n-1;i>=0;--i)inv[i]=1ll*inv[i+1]*(i+1)%mod;
for(int i=1;i<n;++i)rev[i]=(rev[i>>1]>>1)|((i&1)<<18);
}
inline void NTT(int n,int *a,int op){
for(int i=1;i<n;++i)if(i<rev[i])swap(a[i],a[rev[i]]);
for(int l=1;l<<1<=n;l<<=1){
int W=qpow(G,(mod-1)/(l<<1));
for(int i=1;i<l;++i)w[i]=1ll*w[i-1]*W%mod;
for(int i=0;i+(l<<1)<=n;i+=l<<1){
for(int j=0;j<l;++j){
int x=a[i+j],y=1ll*a[i+j+l]*w[j]%mod;
a[i+j]=Add(x,y),a[i+j+l]=Add(x,mod-y);
}
}
}
if(op==-1){
int inv=qpow(n,mod-2);
reverse(a+1,a+n);
for(int i=0;i<n;++i)a[i]=1ll*a[i]*inv%mod;
}
}
struct Cx{
int i,l,r,Res;
inline void pre(){i=l=r=0,Res=1;}
inline int ask(int I,int ql,int qr){
for(;i<I;++i){
Res=2ll*Res%mod;
Res=Add(Res,C(i,l-1));
Res=Add(Res,mod-C(i,r));
}
while(l<ql)Res=Add(Res,mod-C(i,l)),++l;
while(r>qr)Res=Add(Res,mod-C(i,r)),--r;
while(l>ql)--l,Res=Add(Res,C(i,l));
while(r<qr)++r,Res=Add(Res,C(i,r));
return Res;
}
}cx[N];
inline void Calc(int *f,int n,int a){
if(1ll*n*a<=3e8){
memset(dp,0,sizeof(dp));
int now=1,pre=0;
f[0]=1;
for(int i=1;i<=n;++i)dp[now][i]=1;
for(int i=1;i<=d;++i){
now^=1,pre^=1;
for(int j=1;j<=n;++j){
dp[now][j]=0;
if(j!=1)dp[now][j]=Add(dp[now][j],dp[pre][j-1]);
if(j!=n)dp[now][j]=Add(dp[now][j],dp[pre][j+1]);
}
f[i]=dp[now][a];
}
}else{
++n;
int l=(a-d-n+1)/n,r=(a+d-1)/n;
for(int i=l;i<=r;++i)cx[i-l].pre();
for(int i=0;i<=d;++i){
for(int j=l;j<=r;++j){
int ql=(i+j*n-a+2)>>1,qr=(i+n+j*n-a-1)>>1;
f[i]=Add(f[i],(j&1?mod-1ll:1ll)*cx[j-l].ask(i,ql,qr)%mod);
}
}
}
}
signed main(){
// freopen("bacteria.in","r",stdin);
// freopen("bacteria.out","w",stdout);
std::ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>d>>n>>m>>k>>a>>b>>c;
pre(lim),Calc(f,n,a),Calc(g,m,b),Calc(h,k,c);
for(int i=0;i<=d;++i)f[i]=1ll*f[i]*inv[i]%mod,g[i]=1ll*g[i]*inv[i]%mod,h[i]=1ll*h[i]*inv[i]%mod;
NTT(lim,f,1),NTT(lim,g,1),NTT(lim,h,1);
for(int i=0;i<lim;++i)f[i]=1ll*f[i]*g[i]%mod*h[i]%mod;
NTT(lim,f,-1);
cout<<1ll*f[d]*fac[d]%mod;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 5
Accepted
Test #1:
score: 5
Accepted
time: 74ms
memory: 23324kb
input:
50 41 46 42 8 20 21
output:
791406134
result:
ok 1 number(s): "791406134"
Test #2:
score: 0
Accepted
time: 71ms
memory: 23280kb
input:
50 49 44 48 49 15 25
output:
544847893
result:
ok 1 number(s): "544847893"
Subtask #2:
score: 10
Accepted
Dependency #1:
100%
Accepted
Test #3:
score: 10
Accepted
time: 166ms
memory: 23384kb
input:
5000 4994 4990 4990 976 2257 2505
output:
836390717
result:
ok 1 number(s): "836390717"
Test #4:
score: 0
Accepted
time: 166ms
memory: 23512kb
input:
5000 4994 4997 4994 4399 1826 1332
output:
65414465
result:
ok 1 number(s): "65414465"
Subtask #3:
score: 15
Accepted
Test #5:
score: 15
Accepted
time: 111ms
memory: 23508kb
input:
120000 300 1 1 141 1 1
output:
637174
result:
ok 1 number(s): "637174"
Test #6:
score: 0
Accepted
time: 211ms
memory: 23468kb
input:
120000 994 1 1 15 1 1
output:
218803691
result:
ok 1 number(s): "218803691"
Test #7:
score: 0
Accepted
time: 77ms
memory: 23136kb
input:
120000 119999 1 1 19896 1 1
output:
68846585
result:
ok 1 number(s): "68846585"
Subtask #4:
score: 10
Accepted
Test #8:
score: 10
Accepted
time: 85ms
memory: 22956kb
input:
119000 119991 119991 1 23819 52139 1
output:
944500934
result:
ok 1 number(s): "944500934"
Subtask #5:
score: 0
Time Limit Exceeded
Dependency #4:
100%
Accepted
Test #9:
score: 0
Time Limit Exceeded
input:
120000 13997 13996 1 42 9266 1
output:
result:
Subtask #6:
score: 0
Skipped
Dependency #3:
100%
Accepted
Dependency #5:
0%
Subtask #7:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
100%
Accepted
Dependency #5:
0%