QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#400672 | #4903. 细菌 | zwh2008 | 100 ✓ | 845ms | 19164kb | C++14 | 2.4kb | 2024-04-27 14:56:14 | 2024-04-27 14:56:14 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using pi=pair<int,int>;
#define fi first
#define se second
const int N=3e5+5,mod=998244353;
int A,B,C,X,Y,Z,k,rev[N];
ll ans,i3,fx[N],fy[N],fz[N],fc[N],inv[N],f[2][N];
ll qp(ll a,int b){ll ans=1;for(;b;b>>=1,a=a*a%mod)if(b&1)ans=ans*a%mod;return ans;}
void init(int n) {
fc[0]=1,i3=qp(3,mod-2);for(int i=1;i<=n;i++)fc[i]=fc[i-1]*i%mod;
inv[n]=qp(fc[n],mod-2);for(int i=n-1;~i;i--)inv[i]=inv[i+1]*(i+1)%mod;
}
ll comb(int n,int m){return n<m||m<0?0:fc[n]*inv[n-m]%mod*inv[m]%mod;}
inline ll md(ll x){return x<mod?x:x-mod;}
void NTT(ll*a,int l,int op) {
for(int i=0;i<l;i++)if(i<rev[i])swap(a[i],a[rev[i]]);
for(int i=1;i<l;i<<=1) {
ll wn=qp(op?3:i3,(mod-1)/(i<<1));
for(int j=0;j<l;j+=i<<1) {
ll w=1,x,y;
for(int k=0;k<i;k++,w=w*wn%mod)x=a[j+k],y=a[i+j+k]*w%mod,a[j+k]=md(x+y),a[i+j+k]=md(x-y+mod);
}
}
}
void slv(ll*a,int n,int m) {
auto doit=[&](int l,int r,int op) {
int L=0,R=-1;ll s=0;
for(int i=0;i<=k;i++) {
int nl=max(0,(int)ceil((i+m-r)/2.0)),nr=min(i,(int)floor((i+m-l)/2.0));
s=(s*2+comb(i-1,L-1)-comb(i-1,R)+mod)%mod;
if(nl>nr)continue;
while(R<nr)s=(s+comb(i,++R))%mod;
while(L<nl)s=(s+mod-comb(i,L++))%mod;
a[i]=(a[i]+op*s+mod)%mod;
}
};
if(1ll*n*k<=3e8) {
memset(f,0,sizeof(f));
for(int i=1;i<=n;i++)f[0][i]=1;
a[0]=1;
for(int i=1;i<=k;a[i]=(a[i]+f[i&1][m])%mod,i++)
for(int j=1;j<=n;j++)f[i&1][j]=(f[i-1&1][j-1]+f[i-1&1][j+1])%mod;
}else {
int l=1,r=n;doit(l,r,1);
for(int o=1;;o++) {
if(o&1)swap(l,r),l=-l,r=-r;else swap(l,r),l=2*(n+1)-l,r=2*(n+1)-r;
if(l>3*max(n,k)||r<-3*max(n,k))break;
doit(l,r,(o&1?-1:1));
}l=1,r=n;
for(int o=0;;o++) {
if(o&1)swap(l,r),l=-l,r=-r;else swap(l,r),l=2*(n+1)-l,r=2*(n+1)-r;
if(l>3*max(n,k)||r<-3*max(n,k))break;
doit(l,r,(o&1?1:-1));
}
}
}
int main() {
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>k>>A>>B>>C>>X>>Y>>Z,init(3e5);
slv(fx,A,X),slv(fy,B,Y),slv(fz,C,Z);
int l=1,r=0;while(l<=k*2)l<<=1,r++;
for(int i=0;i<l;i++)rev[i]=rev[i>>1]>>1|(i&1)<<r-1;
for(int i=0;i<=k;i++)fx[i]=fx[i]*inv[i]%mod,fy[i]=fy[i]*inv[i]%mod;
NTT(fx,l,1),NTT(fy,l,1);
for(int i=0;i<l;i++)fx[i]=fx[i]*fy[i]%mod;
NTT(fx,l,0);ll invl=qp(l,mod-2);
for(int i=0;i<l;i++)fx[i]=fx[i]*invl%mod;
for(int i=0;i<=k;i++)ans=(ans+fx[i]*fz[k-i]%mod*inv[k-i])%mod;
cout<<ans*fc[k]%mod<<'\n';
return 0;
}
詳細信息
Subtask #1:
score: 5
Accepted
Test #1:
score: 5
Accepted
time: 7ms
memory: 12996kb
input:
50 41 46 42 8 20 21
output:
791406134
result:
ok 1 number(s): "791406134"
Test #2:
score: 5
Accepted
time: 3ms
memory: 13052kb
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: 91ms
memory: 13464kb
input:
5000 4994 4990 4990 976 2257 2505
output:
836390717
result:
ok 1 number(s): "836390717"
Test #4:
score: 10
Accepted
time: 84ms
memory: 13348kb
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: 90ms
memory: 19164kb
input:
120000 300 1 1 141 1 1
output:
637174
result:
ok 1 number(s): "637174"
Test #6:
score: 15
Accepted
time: 176ms
memory: 19104kb
input:
120000 994 1 1 15 1 1
output:
218803691
result:
ok 1 number(s): "218803691"
Test #7:
score: 15
Accepted
time: 50ms
memory: 19104kb
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: 53ms
memory: 19096kb
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: 163ms
memory: 19164kb
input:
120000 13997 13996 1 42 9266 1
output:
775637357
result:
ok 1 number(s): "775637357"
Test #10:
score: 15
Accepted
time: 158ms
memory: 19092kb
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: 120ms
memory: 19040kb
input:
120000 294 296 1 142 273 1
output:
889786082
result:
ok 1 number(s): "889786082"
Test #12:
score: 35
Accepted
time: 156ms
memory: 19088kb
input:
120000 395 390 1 370 185 1
output:
884557050
result:
ok 1 number(s): "884557050"
Test #13:
score: 35
Accepted
time: 176ms
memory: 19160kb
input:
120000 491 495 1 430 25 1
output:
272929924
result:
ok 1 number(s): "272929924"
Test #14:
score: 35
Accepted
time: 207ms
memory: 19120kb
input:
120000 590 593 1 418 459 1
output:
446962505
result:
ok 1 number(s): "446962505"
Test #15:
score: 35
Accepted
time: 216ms
memory: 19104kb
input:
120000 697 690 1 166 450 1
output:
216092107
result:
ok 1 number(s): "216092107"
Test #16:
score: 35
Accepted
time: 251ms
memory: 19044kb
input:
120000 793 799 1 416 61 1
output:
661260042
result:
ok 1 number(s): "661260042"
Test #17:
score: 35
Accepted
time: 313ms
memory: 19160kb
input:
120000 1000 1000 1 613 547 1
output:
429669083
result:
ok 1 number(s): "429669083"
Test #18:
score: 35
Accepted
time: 568ms
memory: 19160kb
input:
120000 1993 1995 1 493 565 1
output:
609392900
result:
ok 1 number(s): "609392900"
Test #19:
score: 35
Accepted
time: 364ms
memory: 19036kb
input:
120000 4995 4998 1 3166 3765 1
output:
394497547
result:
ok 1 number(s): "394497547"
Test #20:
score: 35
Accepted
time: 201ms
memory: 19116kb
input:
120000 9994 9991 1 6099 691 1
output:
795651799
result:
ok 1 number(s): "795651799"
Test #21:
score: 35
Accepted
time: 67ms
memory: 19048kb
input:
120000 49990 49990 1 41933 2862 1
output:
360787513
result:
ok 1 number(s): "360787513"
Test #22:
score: 35
Accepted
time: 62ms
memory: 19164kb
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: 160ms
memory: 19108kb
input:
120000 296 300 297 89 130 280
output:
702788425
result:
ok 1 number(s): "702788425"
Test #24:
score: 10
Accepted
time: 204ms
memory: 19108kb
input:
120000 392 397 391 222 280 10
output:
322470184
result:
ok 1 number(s): "322470184"
Test #25:
score: 10
Accepted
time: 243ms
memory: 19120kb
input:
120000 499 498 500 263 315 367
output:
449848666
result:
ok 1 number(s): "449848666"
Test #26:
score: 10
Accepted
time: 278ms
memory: 19124kb
input:
120000 598 591 594 497 474 400
output:
35486519
result:
ok 1 number(s): "35486519"
Test #27:
score: 10
Accepted
time: 327ms
memory: 19164kb
input:
120000 694 692 695 625 173 477
output:
785203749
result:
ok 1 number(s): "785203749"
Test #28:
score: 10
Accepted
time: 365ms
memory: 19100kb
input:
120000 794 796 800 395 465 507
output:
897269426
result:
ok 1 number(s): "897269426"
Test #29:
score: 10
Accepted
time: 439ms
memory: 19060kb
input:
120000 993 998 991 196 712 911
output:
464727191
result:
ok 1 number(s): "464727191"
Test #30:
score: 10
Accepted
time: 845ms
memory: 19108kb
input:
120000 1991 2000 1994 1937 1362 1494
output:
473701811
result:
ok 1 number(s): "473701811"
Test #31:
score: 10
Accepted
time: 518ms
memory: 14360kb
input:
120000 4994 4990 4990 646 1214 2276
output:
763540821
result:
ok 1 number(s): "763540821"
Test #32:
score: 10
Accepted
time: 286ms
memory: 14424kb
input:
120000 9994 9992 9991 6588 9538 2632
output:
804858722
result:
ok 1 number(s): "804858722"
Test #33:
score: 10
Accepted
time: 98ms
memory: 14420kb
input:
120000 49997 49997 49993 46278 44140 26931
output:
139550295
result:
ok 1 number(s): "139550295"
Test #34:
score: 10
Accepted
time: 68ms
memory: 14484kb
input:
120000 119997 120000 120000 24867 116477 35338
output:
946147605
result:
ok 1 number(s): "946147605"