QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#87612 | #4903. 细菌 | Pure_Furies | 100 ✓ | 2000ms | 17444kb | C++14 | 2.4kb | 2023-03-13 21:15:09 | 2023-03-13 21:15:16 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int mod=998244353,ggg=3,invggg=(mod+1)/ggg;
const int maxn=524288;
int mypow(int x,int y){
int ret=1;
while(y){
if(y&1)ret=1ll*ret*x%mod;
y>>=1;x=1ll*x*x%mod;
}return ret;
}
int revs[maxn];
void initrev(int Len){
for(int i=1;i<Len;++i){
revs[i]=revs[i>>1]>>1;
if(i&1)revs[i]|=(Len>>1);
}
}
void DFT(int *f,int n,int rev){
int g0=rev==1?ggg:invggg;
initrev(n);
for(register int i=0;i<n;++i)
if(i<revs[i])
f[i]^=f[revs[i]]^=f[i]^=f[revs[i]];
for(register int h=2;h<=n;h<<=1){
int gn=mypow(g0,(mod-1)/h);
for(register int j=0;j<n;j+=h){
int gk=1;
for(register int k=j;k<j+(h>>1);++k){
int e=f[k],o=1ll*gk*f[k+(h>>1)]%mod;
f[k]=(e+o)%mod,f[k+(h>>1)]=(e+mod-o)%mod;
gk=1ll*gk*gn%mod;
}
}
}
if(rev==-1){
int invv=mypow(n,mod-2);
for(register int i=0;i<n;++i)
f[i]=1ll*f[i]*invv%mod;
}
}
int fac[maxn],inv[maxn];
int C(int x,int y){
if(x<y||y<0)return 0;
return 1ll*fac[x]*inv[y]%mod*inv[x-y]%mod;
}
struct node{
int p,l,r,w;
void init(){p=0;l=0;r=0;w=1;}
int calc(int qp,int ql,int qr){
while(p<qp)w=(2ll*w+C(p,l-1)-C(p,r)+mod)%mod,p++;
while(l<ql)w=(w-C(p,l++)+mod)%mod;
while(l>ql)w=(w+C(p,--l))%mod;
while(r>qr)w=(w-C(p,r--)+mod)%mod;
while(r<qr)w=(w+C(p,++r))%mod;
return w;
}
}w[120003];
const int B=1000;
int dp[2][B+3],d;
void calc(int *f,int n,int p){
if(n<=B){
memset(dp,0,sizeof(dp));
for(int i=0;i<n;i++)
dp[0][i]=1;
f[0]=1;
for(int i=1;i<=d;i++){
for(int j=0;j<n;j++){
dp[i&1][j]=(j?dp[i-1&1][j-1]:0)+(j<n-1?dp[i-1&1][j+1]:0);
if(dp[i&1][j]>=mod)dp[i&1][j]-=mod;
}f[i]=dp[i&1][p-1];
}return;
}else{
int l=(p-d-n)/(n+1),r=(d+p-1)/(n+1);
for(int i=l;i<=r;i++)
w[i-l].init();
for(int i=0;i<=d;i++)
for(int j=l;j<=r;j++)
f[i]=(f[i]+(j%2?mod-1ll:1ll)*w[j-l].calc(i,(i-p+2+j*(n+1))>>1,(i-p+n)+j*(n+1)>>1))%mod;
}
}
int n,m,k,a,b,c;
int f[maxn],g[maxn],h[maxn];
int main(){
cin>>d>>n>>m>>k>>a>>b>>c;
fac[0]=1;
for(int i=1;i<maxn;i++)
fac[i]=1ll*fac[i-1]*i%mod;
for(int i=0;i<maxn;i++)
inv[i]=mypow(fac[i],mod-2);
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;
DFT(f,maxn,1);
DFT(g,maxn,1);
DFT(h,maxn,1);
for(int i=0;i<maxn;i++)
f[i]=1ll*f[i]*g[i]%mod*h[i]%mod;
DFT(f,maxn,-1);
cout<<1ll*f[d]*fac[d]%mod;
}
詳細信息
Subtask #1:
score: 5
Accepted
Test #1:
score: 5
Accepted
time: 202ms
memory: 17428kb
input:
50 41 46 42 8 20 21
output:
791406134
result:
ok 1 number(s): "791406134"
Test #2:
score: 0
Accepted
time: 201ms
memory: 17360kb
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: 201ms
memory: 16236kb
input:
5000 4994 4990 4990 976 2257 2505
output:
836390717
result:
ok 1 number(s): "836390717"
Test #4:
score: 0
Accepted
time: 206ms
memory: 15756kb
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: 379ms
memory: 16996kb
input:
120000 300 1 1 141 1 1
output:
637174
result:
ok 1 number(s): "637174"
Test #6:
score: 0
Accepted
time: 797ms
memory: 17444kb
input:
120000 994 1 1 15 1 1
output:
218803691
result:
ok 1 number(s): "218803691"
Test #7:
score: 0
Accepted
time: 213ms
memory: 16168kb
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: 220ms
memory: 16652kb
input:
119000 119991 119991 1 23819 52139 1
output:
944500934
result:
ok 1 number(s): "944500934"
Subtask #5:
score: 15
Accepted
Dependency #4:
100%
Accepted
Test #9:
score: 15
Accepted
time: 264ms
memory: 17260kb
input:
120000 13997 13996 1 42 9266 1
output:
775637357
result:
ok 1 number(s): "775637357"
Test #10:
score: 0
Accepted
time: 281ms
memory: 17140kb
input:
120000 13997 13997 1 9768 6131 1
output:
151873213
result:
ok 1 number(s): "151873213"
Subtask #6:
score: 35
Accepted
Dependency #3:
100%
Accepted
Dependency #5:
100%
Accepted
Test #11:
score: 35
Accepted
time: 566ms
memory: 16008kb
input:
120000 294 296 1 142 273 1
output:
889786082
result:
ok 1 number(s): "889786082"
Test #12:
score: 0
Accepted
time: 660ms
memory: 17444kb
input:
120000 395 390 1 370 185 1
output:
884557050
result:
ok 1 number(s): "884557050"
Test #13:
score: 0
Accepted
time: 794ms
memory: 16748kb
input:
120000 491 495 1 430 25 1
output:
272929924
result:
ok 1 number(s): "272929924"
Test #14:
score: 0
Accepted
time: 920ms
memory: 15904kb
input:
120000 590 593 1 418 459 1
output:
446962505
result:
ok 1 number(s): "446962505"
Test #15:
score: 0
Accepted
time: 1042ms
memory: 16368kb
input:
120000 697 690 1 166 450 1
output:
216092107
result:
ok 1 number(s): "216092107"
Test #16:
score: 0
Accepted
time: 1154ms
memory: 16000kb
input:
120000 793 799 1 416 61 1
output:
661260042
result:
ok 1 number(s): "661260042"
Test #17:
score: 0
Accepted
time: 1402ms
memory: 17204kb
input:
120000 1000 1000 1 613 547 1
output:
429669083
result:
ok 1 number(s): "429669083"
Test #18:
score: 0
Accepted
time: 696ms
memory: 15980kb
input:
120000 1993 1995 1 493 565 1
output:
609392900
result:
ok 1 number(s): "609392900"
Test #19:
score: 0
Accepted
time: 410ms
memory: 16264kb
input:
120000 4995 4998 1 3166 3765 1
output:
394497547
result:
ok 1 number(s): "394497547"
Test #20:
score: 0
Accepted
time: 314ms
memory: 16352kb
input:
120000 9994 9991 1 6099 691 1
output:
795651799
result:
ok 1 number(s): "795651799"
Test #21:
score: 0
Accepted
time: 218ms
memory: 16468kb
input:
120000 49990 49990 1 41933 2862 1
output:
360787513
result:
ok 1 number(s): "360787513"
Test #22:
score: 0
Accepted
time: 206ms
memory: 16692kb
input:
120000 119996 119994 1 58014 49559 1
output:
682979057
result:
ok 1 number(s): "682979057"
Subtask #7:
score: 10
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
100%
Accepted
Dependency #5:
100%
Accepted
Dependency #6:
100%
Accepted
Test #23:
score: 10
Accepted
time: 735ms
memory: 17188kb
input:
120000 296 300 297 89 130 280
output:
702788425
result:
ok 1 number(s): "702788425"
Test #24:
score: 0
Accepted
time: 903ms
memory: 16328kb
input:
120000 392 397 391 222 280 10
output:
322470184
result:
ok 1 number(s): "322470184"
Test #25:
score: 0
Accepted
time: 1113ms
memory: 16536kb
input:
120000 499 498 500 263 315 367
output:
449848666
result:
ok 1 number(s): "449848666"
Test #26:
score: 0
Accepted
time: 1280ms
memory: 15588kb
input:
120000 598 591 594 497 474 400
output:
35486519
result:
ok 1 number(s): "35486519"
Test #27:
score: 0
Accepted
time: 1456ms
memory: 16844kb
input:
120000 694 692 695 625 173 477
output:
785203749
result:
ok 1 number(s): "785203749"
Test #28:
score: 0
Accepted
time: 1665ms
memory: 15728kb
input:
120000 794 796 800 395 465 507
output:
897269426
result:
ok 1 number(s): "897269426"
Test #29:
score: 0
Accepted
time: 2000ms
memory: 17084kb
input:
120000 993 998 991 196 712 911
output:
464727191
result:
ok 1 number(s): "464727191"
Test #30:
score: 0
Accepted
time: 923ms
memory: 16772kb
input:
120000 1991 2000 1994 1937 1362 1494
output:
473701811
result:
ok 1 number(s): "473701811"
Test #31:
score: 0
Accepted
time: 493ms
memory: 17036kb
input:
120000 4994 4990 4990 646 1214 2276
output:
763540821
result:
ok 1 number(s): "763540821"
Test #32:
score: 0
Accepted
time: 344ms
memory: 16836kb
input:
120000 9994 9992 9991 6588 9538 2632
output:
804858722
result:
ok 1 number(s): "804858722"
Test #33:
score: 0
Accepted
time: 217ms
memory: 16692kb
input:
120000 49997 49997 49993 46278 44140 26931
output:
139550295
result:
ok 1 number(s): "139550295"
Test #34:
score: 0
Accepted
time: 222ms
memory: 16496kb
input:
120000 119997 120000 120000 24867 116477 35338
output:
946147605
result:
ok 1 number(s): "946147605"