QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#295909 | #4903. 细菌 | SoyTony | 90 | 1617ms | 16864kb | C++14 | 4.5kb | 2024-01-01 14:51:32 | 2024-01-01 14:51:32 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int maxn=(1<<18)+10;
const int B=800;
const int lim=24e4;
const int mod=998244353;
inline int read(){
int x=0,w=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c<='9'&&c>='0'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
return x*w;
}
inline int q_pow(int A,int B,int P){
int res=1;
while(B){
if(B&1) res=1ll*res*A%P;
A=1ll*A*A%P;
B>>=1;
}
return res;
}
int fact[maxn],inv_fact[maxn];
inline int C(int N,int M){
if(M<0) return 0;
if(N<M) return 0;
return 1ll*fact[N]*inv_fact[M]%mod*inv_fact[N-M]%mod;
}
int rev[maxn];
int base,w[maxn];
struct Poly{
const static int g=3;
int deg;
vector<ull> f;
ull &operator[](const int &i){return f[i];}
ull operator[](const int &i)const{return f[i];}
inline void set(int L){deg=L;f.resize(L);}
inline void clear(int L,int R){for(int i=L;i<=R;++i)f[i]=0;}
inline void output(int L){for(int i=0;i<L;++i)printf("%llu ",f[i]);printf("\n");}
inline void NTT(int L,bool type){
set(L);
for(int i=1;i<L;++i){
rev[i]=(rev[i>>1]>>1)+(i&1?L>>1:0);
if(i<rev[i]) swap(f[i],f[rev[i]]);
}
for(int d=1;d<L;d<<=1){
base=q_pow(type?g:q_pow(g,mod-2,mod),(mod-1)/(2*d),mod);
w[0]=1;
for(int i=1;i<d;++i) w[i]=1ll*w[i-1]*base%mod;
for(int i=0;i<L;i+=d<<1){
for(int j=0;j<d;++j){
ull x=f[i+j],y=f[i+d+j]*w[j]%mod;
f[i+j]=x+y,f[i+d+j]=x-y+mod;
}
}
}
for(int i=0;i<L;++i) f[i]%=mod;
if(!type){
int inv_L=q_pow(L,mod-2,mod);
for(int i=0;i<L;++i) f[i]=f[i]*inv_L%mod;
}
}
}F,G,H;
inline void calc(int t,int R,vector<int> &f,int coef){
// cerr<<"calc t:"<<t<<" R:"<<R<<" coef:"<<coef<<endl;
if(R<0) return;
int S1=1,S2=0;
for(int i=1;i<=t;++i){
S1=(2ll*S1-C(i-1,(i-1+R)/2)+mod)%mod;
S2=(2ll*S2-C(i-1,i/2-1)+mod)%mod;
if(!((i+R)&1)) S1=(S1+C(i,(i+R)/2))%mod;
if(i&1) S2=(S2+C(i,(i+1)/2-1))%mod;
// cerr<<"i:"<<i<<" S1:"<<S1<<" S2:"<<S2<<endl;
f[i]=(f[i]+1ll*coef*(S1-S2+mod)%mod+mod)%mod;
}
}
int dp[2][maxn];
inline void solve(int t,int n,int a,vector<int> &f){
f.push_back(1);
if(n<=B){
for(int i=1;i<=n;++i) dp[0][i]=dp[1][i]=0;
dp[0][a]=1;
for(int i=1;i<=t;++i){
for(int j=1;j<=n;++j){
if(j>1) dp[i&1][j-1]=(dp[i&1][j-1]+dp[i&1^1][j])%mod;
if(j<n) dp[i&1][j+1]=(dp[i&1][j+1]+dp[i&1^1][j])%mod;
}
int sum=0;
for(int j=1;j<=n;++j){
sum=(sum+dp[i&1][j])%mod;
dp[i&1^1][j]=0;
}
sum=1ll*sum*inv_fact[i]%mod;
f.push_back(sum);
}
}
else{
for(int i=1;i<=t;++i) f.push_back(0);
for(int i=-((t-1)/n+1)-1;i<=(t-1)/n+1;++i){
int l=i*(n+1)+1,r=(i+1)*(n+1)-1,L,R;
// cerr<<"i:"<<i<<" ["<<l<<","<<r<<"]"<<endl;
if(!i){
L=0,R=r-a;
calc(t,R,f,1);
L=1,R=a-l;
calc(t,R,f,1);
calc(t,L-1,f,-1);
}
else if(i>0){
L=l-a,R=r-a;
calc(t,R,f,(i&1)?-1:1);
calc(t,L-1,f,(i&1)?1:-1);
}
else{
L=a-r,R=a-l;
calc(t,R,f,((-i)&1)?-1:1);
calc(t,L-1,f,((-i)&1)?1:-1);
}
}
for(int i=1;i<=t;++i) f[i]=1ll*f[i]*inv_fact[i]%mod;
}
}
int t,n,m,k,a,b,c;
vector<int> f,g,h;
int ans;
int main(){
fact[0]=1;
for(int i=1;i<=lim;++i) fact[i]=1ll*fact[i-1]*i%mod;
inv_fact[0]=1,inv_fact[lim]=q_pow(fact[lim],mod-2,mod);
for(int i=lim-1;i>=1;--i) inv_fact[i]=1ll*inv_fact[i+1]*(i+1)%mod;
t=read(),n=read(),m=read(),k=read(),a=read(),b=read(),c=read();
solve(t,n,a,f);
solve(t,m,b,g);
solve(t,k,c,h);
int L=1;
while(L<2*t) L<<=1;
F.set(L),G.set(L),H.set(L);
for(int i=0;i<=t;++i) F[i]=f[i],G[i]=g[i];
F.NTT(L,1),G.NTT(L,1);
for(int i=0;i<L;++i) H[i]=1ll*F[i]*G[i]%mod;
H.NTT(L,0);
for(int i=0;i<=t;++i) ans=(ans+1ll*H[i]*h[t-i])%mod;
ans=1ll*ans*fact[t]%mod;
printf("%d\n",ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 5
Accepted
Test #1:
score: 5
Accepted
time: 3ms
memory: 9576kb
input:
50 41 46 42 8 20 21
output:
791406134
result:
ok 1 number(s): "791406134"
Test #2:
score: 0
Accepted
time: 3ms
memory: 7904kb
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: 7ms
memory: 8680kb
input:
5000 4994 4990 4990 976 2257 2505
output:
836390717
result:
ok 1 number(s): "836390717"
Test #4:
score: 0
Accepted
time: 7ms
memory: 9948kb
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: 206ms
memory: 15260kb
input:
120000 300 1 1 141 1 1
output:
637174
result:
ok 1 number(s): "637174"
Test #6:
score: 0
Accepted
time: 825ms
memory: 16492kb
input:
120000 994 1 1 15 1 1
output:
218803691
result:
ok 1 number(s): "218803691"
Test #7:
score: 0
Accepted
time: 44ms
memory: 15964kb
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: 51ms
memory: 15312kb
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: 152ms
memory: 15560kb
input:
120000 13997 13996 1 42 9266 1
output:
775637357
result:
ok 1 number(s): "775637357"
Test #10:
score: 0
Accepted
time: 152ms
memory: 15336kb
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: 389ms
memory: 15240kb
input:
120000 294 296 1 142 273 1
output:
889786082
result:
ok 1 number(s): "889786082"
Test #12:
score: 0
Accepted
time: 507ms
memory: 15920kb
input:
120000 395 390 1 370 185 1
output:
884557050
result:
ok 1 number(s): "884557050"
Test #13:
score: 0
Accepted
time: 632ms
memory: 16704kb
input:
120000 491 495 1 430 25 1
output:
272929924
result:
ok 1 number(s): "272929924"
Test #14:
score: 0
Accepted
time: 755ms
memory: 16000kb
input:
120000 590 593 1 418 459 1
output:
446962505
result:
ok 1 number(s): "446962505"
Test #15:
score: 0
Accepted
time: 873ms
memory: 16000kb
input:
120000 697 690 1 166 450 1
output:
216092107
result:
ok 1 number(s): "216092107"
Test #16:
score: 0
Accepted
time: 1002ms
memory: 16528kb
input:
120000 793 799 1 416 61 1
output:
661260042
result:
ok 1 number(s): "661260042"
Test #17:
score: 0
Accepted
time: 1617ms
memory: 16180kb
input:
120000 1000 1000 1 613 547 1
output:
429669083
result:
ok 1 number(s): "429669083"
Test #18:
score: 0
Accepted
time: 832ms
memory: 16864kb
input:
120000 1993 1995 1 493 565 1
output:
609392900
result:
ok 1 number(s): "609392900"
Test #19:
score: 0
Accepted
time: 360ms
memory: 15508kb
input:
120000 4995 4998 1 3166 3765 1
output:
394497547
result:
ok 1 number(s): "394497547"
Test #20:
score: 0
Accepted
time: 204ms
memory: 15928kb
input:
120000 9994 9991 1 6099 691 1
output:
795651799
result:
ok 1 number(s): "795651799"
Test #21:
score: 0
Accepted
time: 73ms
memory: 15788kb
input:
120000 49990 49990 1 41933 2862 1
output:
360787513
result:
ok 1 number(s): "360787513"
Test #22:
score: 0
Accepted
time: 59ms
memory: 15744kb
input:
120000 119996 119994 1 58014 49559 1
output:
682979057
result:
ok 1 number(s): "682979057"
Subtask #7:
score: 0
Time Limit Exceeded
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: 561ms
memory: 16152kb
input:
120000 296 300 297 89 130 280
output:
702788425
result:
ok 1 number(s): "702788425"
Test #24:
score: 0
Accepted
time: 751ms
memory: 16560kb
input:
120000 392 397 391 222 280 10
output:
322470184
result:
ok 1 number(s): "322470184"
Test #25:
score: 0
Accepted
time: 955ms
memory: 15568kb
input:
120000 499 498 500 263 315 367
output:
449848666
result:
ok 1 number(s): "449848666"
Test #26:
score: 0
Accepted
time: 1123ms
memory: 16092kb
input:
120000 598 591 594 497 474 400
output:
35486519
result:
ok 1 number(s): "35486519"
Test #27:
score: 0
Accepted
time: 1316ms
memory: 15968kb
input:
120000 694 692 695 625 173 477
output:
785203749
result:
ok 1 number(s): "785203749"
Test #28:
score: 0
Accepted
time: 1506ms
memory: 15508kb
input:
120000 794 796 800 395 465 507
output:
897269426
result:
ok 1 number(s): "897269426"
Test #29:
score: -10
Time Limit Exceeded
input:
120000 993 998 991 196 712 911