QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#91117 | #4903. 细菌 | wyzwyz | 100 ✓ | 749ms | 14452kb | C++14 | 3.1kb | 2023-03-27 13:02:13 | 2023-03-27 13:02:14 |
Judging History
answer
#include<cstdio>
#include<cctype>
#include<cmath>
#define maxn 303303
const int G=3,mod=998244353;
template<class T>
inline T read(){
T r=0,f=0;
char c;
while(!isdigit(c=getchar()))f|=(c=='-');
while(isdigit(c))r=(r*10)+(c^48),c=getchar();
return f?-r:r;
}
template<class T>
inline T abs(T a){
return a<0?-a:a;
}
template<class T>
inline T min(T a,T b){
return a<b?a:b;
}
inline long long qpow(long long a,int b){
long long ans=1;
for(;b;b>>=1){
if(b&1)(ans*=a)%=mod;
(a*=a)%=mod;
}
return ans;
}
unsigned long long A[maxn];
namespace Polyn{
const int N=262144;
int rev[maxn];
long long g[maxn];
inline void init(){
for(int i=1;i<N;i++)
rev[i]=(rev[i>>1]>>1)|(i&1?N>>1:0);
for(int i=1,p;i<N;i<<=1){
g[i]=1,p=i<<1;
long long x=qpow(G,(mod-1)/p);
for(int j=i+1;j<p;j++)
g[j]=g[j-1]*x%mod;
}
}
inline void NTT(long long *f,int opt){
for(int i=0;i<N;i++)
A[i]=f[rev[i]];
for(int i=1;i<N;i<<=1)
for(int j=0,p=i<<1;j<N;j+=p)
for(int k=0;k<i;k++){
int l=j|k,r=i|l;
int val=A[r]*g[i|k]%mod;
A[r]=A[l]+mod-val,A[l]+=val;
}
if(!opt){
for(int i=0;i<N;i++)
f[i]=A[i]%mod;
return;
}
int invn=mod-(mod-1)/N;
f[0]=A[0]%mod*invn%mod;
for(int i=1;i<N;i++)
f[i]=A[N-i]%mod*invn%mod;
}
}
int T,n,m,K,X,Y,Z;
long long pw[maxn],frac[maxn],invf[maxn];
inline void init(int n){
pw[0]=1,frac[0]=1;
for(int i=1;i<=n;i++){
pw[i]=pw[i-1]*2%mod;
frac[i]=frac[i-1]*i%mod;
}
invf[n]=qpow(frac[n],mod-2);
for(int i=n;i;i--)
invf[i-1]=invf[i]*i%mod;
}
inline long long C(int n,int m){
return frac[n]*invf[m]%mod*invf[n-m]%mod;
}
inline long long F(int n,int d){
if(d>n||(abs(n-d)&1))return 0;
return C(n,(n-d)/2);
}
long long f[maxn],g[maxn],h[maxn];
inline long long Calc(int n,int N,int X,int pos){
long long ans=F(n,abs(X-pos));
long long x=X;
for(int o=0;;o=!o){//A...
if(!o)x=-x;
else x=2*(N+1)-x;
if(abs(x-pos)>n)break;
ans+=(o?1:-1)*F(n,abs(x-pos));
}
x=X;
for(int o=1;;o=!o){//A...
if(!o)x=-x;
else x=2*(N+1)-x;
if(abs(x-pos)>n)break;
ans+=(o?-1:1)*F(n,abs(x-pos));
}
return (ans%mod+mod)%mod;
}
inline void calc(int N,int X,long long *f){
if(N==1)return f[0]=1,void();
if(N<=sqrt(T)){
static long long g[maxn],h[maxn];
for(int i=1;i<=N;i++)g[i]=0;
g[X]=1;
for(int t=0;t<=T;t++){
long long sum=0;
for(int i=1;i<=N;i++)
sum+=g[i],h[i-1]+=g[i],h[i+1]+=g[i];
f[t]=sum%mod*invf[t]%mod,h[0]=h[N+1]=0;
for(int i=1;i<=N;i++)g[i]=h[i]%mod,h[i]=0;
}
return;
}
f[0]=1;
for(int t=1;t<=T;t++)
f[t]=(f[t-1]*2+2*mod-Calc(t-1,N,X,1)-Calc(t-1,N,X,N))%mod;
for(int t=1;t<=T;t++)(f[t]*=invf[t])%=mod;
}
int main(){
init(T=read<int>());
n=read<int>(),m=read<int>(),K=read<int>();
X=read<int>(),Y=read<int>(),Z=read<int>();
calc(n,X,f),calc(m,Y,g),calc(K,Z,h);
Polyn::init();
Polyn::NTT(f,0),Polyn::NTT(g,0);
for(int i=0;i<Polyn::N;i++)(f[i]*=g[i])%=mod;
Polyn::NTT(f,1);
long long ans=0;
for(int i=0;i<=T;i++)
(ans+=f[i]*h[T-i])%=mod;
printf("%lld\n",ans*frac[T]%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: 24ms
memory: 10708kb
input:
50 41 46 42 8 20 21
output:
791406134
result:
ok 1 number(s): "791406134"
Test #2:
score: 0
Accepted
time: 24ms
memory: 10680kb
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: 16ms
memory: 10784kb
input:
5000 4994 4990 4990 976 2257 2505
output:
836390717
result:
ok 1 number(s): "836390717"
Test #4:
score: 0
Accepted
time: 18ms
memory: 10824kb
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: 73ms
memory: 13528kb
input:
120000 300 1 1 141 1 1
output:
637174
result:
ok 1 number(s): "637174"
Test #6:
score: 0
Accepted
time: 110ms
memory: 13480kb
input:
120000 994 1 1 15 1 1
output:
218803691
result:
ok 1 number(s): "218803691"
Test #7:
score: 0
Accepted
time: 20ms
memory: 13440kb
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: 31ms
memory: 13488kb
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: 35ms
memory: 13516kb
input:
120000 13997 13996 1 42 9266 1
output:
775637357
result:
ok 1 number(s): "775637357"
Test #10:
score: 0
Accepted
time: 32ms
memory: 13564kb
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: 111ms
memory: 13468kb
input:
120000 294 296 1 142 273 1
output:
889786082
result:
ok 1 number(s): "889786082"
Test #12:
score: 0
Accepted
time: 497ms
memory: 13492kb
input:
120000 395 390 1 370 185 1
output:
884557050
result:
ok 1 number(s): "884557050"
Test #13:
score: 0
Accepted
time: 407ms
memory: 13456kb
input:
120000 491 495 1 430 25 1
output:
272929924
result:
ok 1 number(s): "272929924"
Test #14:
score: 0
Accepted
time: 369ms
memory: 13492kb
input:
120000 590 593 1 418 459 1
output:
446962505
result:
ok 1 number(s): "446962505"
Test #15:
score: 0
Accepted
time: 299ms
memory: 13432kb
input:
120000 697 690 1 166 450 1
output:
216092107
result:
ok 1 number(s): "216092107"
Test #16:
score: 0
Accepted
time: 264ms
memory: 13512kb
input:
120000 793 799 1 416 61 1
output:
661260042
result:
ok 1 number(s): "661260042"
Test #17:
score: 0
Accepted
time: 260ms
memory: 13468kb
input:
120000 1000 1000 1 613 547 1
output:
429669083
result:
ok 1 number(s): "429669083"
Test #18:
score: 0
Accepted
time: 117ms
memory: 13508kb
input:
120000 1993 1995 1 493 565 1
output:
609392900
result:
ok 1 number(s): "609392900"
Test #19:
score: 0
Accepted
time: 65ms
memory: 13472kb
input:
120000 4995 4998 1 3166 3765 1
output:
394497547
result:
ok 1 number(s): "394497547"
Test #20:
score: 0
Accepted
time: 42ms
memory: 13560kb
input:
120000 9994 9991 1 6099 691 1
output:
795651799
result:
ok 1 number(s): "795651799"
Test #21:
score: 0
Accepted
time: 34ms
memory: 13412kb
input:
120000 49990 49990 1 41933 2862 1
output:
360787513
result:
ok 1 number(s): "360787513"
Test #22:
score: 0
Accepted
time: 19ms
memory: 13504kb
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: 162ms
memory: 14408kb
input:
120000 296 300 297 89 130 280
output:
702788425
result:
ok 1 number(s): "702788425"
Test #24:
score: 0
Accepted
time: 749ms
memory: 14452kb
input:
120000 392 397 391 222 280 10
output:
322470184
result:
ok 1 number(s): "322470184"
Test #25:
score: 0
Accepted
time: 592ms
memory: 14364kb
input:
120000 499 498 500 263 315 367
output:
449848666
result:
ok 1 number(s): "449848666"
Test #26:
score: 0
Accepted
time: 513ms
memory: 14388kb
input:
120000 598 591 594 497 474 400
output:
35486519
result:
ok 1 number(s): "35486519"
Test #27:
score: 0
Accepted
time: 445ms
memory: 14348kb
input:
120000 694 692 695 625 173 477
output:
785203749
result:
ok 1 number(s): "785203749"
Test #28:
score: 0
Accepted
time: 370ms
memory: 14396kb
input:
120000 794 796 800 395 465 507
output:
897269426
result:
ok 1 number(s): "897269426"
Test #29:
score: 0
Accepted
time: 299ms
memory: 14404kb
input:
120000 993 998 991 196 712 911
output:
464727191
result:
ok 1 number(s): "464727191"
Test #30:
score: 0
Accepted
time: 166ms
memory: 14376kb
input:
120000 1991 2000 1994 1937 1362 1494
output:
473701811
result:
ok 1 number(s): "473701811"
Test #31:
score: 0
Accepted
time: 79ms
memory: 14448kb
input:
120000 4994 4990 4990 646 1214 2276
output:
763540821
result:
ok 1 number(s): "763540821"
Test #32:
score: 0
Accepted
time: 46ms
memory: 14440kb
input:
120000 9994 9992 9991 6588 9538 2632
output:
804858722
result:
ok 1 number(s): "804858722"
Test #33:
score: 0
Accepted
time: 32ms
memory: 14380kb
input:
120000 49997 49997 49993 46278 44140 26931
output:
139550295
result:
ok 1 number(s): "139550295"
Test #34:
score: 0
Accepted
time: 36ms
memory: 14428kb
input:
120000 119997 120000 120000 24867 116477 35338
output:
946147605
result:
ok 1 number(s): "946147605"