QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#400700 | #4903. 细菌 | wdnmdwrnmmp | 100 ✓ | 547ms | 19340kb | C++14 | 3.6kb | 2024-04-27 15:15:54 | 2024-04-27 15:15:56 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
typedef vector<int> vi;
typedef pair<int,int> pi;
const int N=1<<18, mod=998244353;
int md(const int &x){
return x>=mod? x-mod: x;
}
int qpow(int x,int y){
int res=1;
while(y){
if(y%2) res=res*x%mod;
x=x*x%mod;
y/=2;
}
return res;
}int inv(int x){return qpow(x,mod-2);}
int fac[N],ifac[N],P[N];
void init(){
fac[0]=1;
rep(i,1,N-1){
fac[i]=fac[i-1]*i%mod;
}
ifac[N-1]=inv(fac[N-1]);
per(i,N-1,1){
ifac[i-1]=ifac[i]*i%mod;
}
rep(i,0,17){
int stp=qpow(3,(mod-1)>>(i+1));
P[1<<i]=1;
rep(j,(1<<i)+1,(2<<i)-1){
P[j]=P[j-1]*stp%mod;
}
}
}
int C(int m,int n){
return n<0 || n>m? 0: fac[m]*ifac[n]%mod*ifac[m-n]%mod;
}
int Sum(int n,int l,int r){
l=max(0ll, l), r=min(n, r);
int res=0;
rep(i,l,r){
res+= C(n,i);
}
return res%mod;
}
void DIF(vi &a){
per(i,17,0){
int len=1<<i;
for(int j=0;j<N;j+=len*2){
int idx=len;
rep(k,j,j+len-1){
int A=a[k], B=a[k+len];
a[k]=md(A+B), a[k+len]=(A-B+mod)*P[idx++]%mod;
}
}
}
}
void DIT(vi &a){
rep(i,0,17){
int len=1<<i;
for(int j=0;j<N;j+=len*2){
int idx=len;
rep(k,j,j+len-1){
int A=a[k], B=a[k+len]*P[idx++]%mod;
a[k]=md(A+B), a[k+len]=md(A-B+mod);
}
}
}
reverse(a.begin()+1,a.end());
int iv=inv(N);
for(int &x:a){
(x*= iv )%=mod;
}
}
vi mul(vi x,vi y){
x.resize(N), y.resize(N);
DIF(x); DIF(y);
rep(i,0,N-1){
(x[i]*= y[i] )%=mod;
}
DIT(x);
return x;
}
vi solve(int n,int a,int d){
if(n==1){
vi res(d+1,0);
res[0]=1;
return res;
}
if(n<=1500){
vi f(n,1),res(d+1,0);
res[0]=1;
rep(i,1,d){
vi tmp(n);
tmp[0]=f[1], tmp[n-1]=f[n-2];
rep(j,1,n-2){
tmp[j]=md(f[j-1]+f[j+1]);
}
swap(f,tmp);
res[i]=f[a]*ifac[i]%mod;
}
return res;
}
else{
vi res(d+1,0);
auto calc=[&](int cx,int op){
{
int cle=cx&1, cri=(cx+n)%2? n-1: n-2;
int dn=0, dl=(cle-cx)/2, dr=(cri-cx)/2;
int csum=Sum(0, dl, dr);
res[0]+=op*csum;
for(int i=2;i<=d;i+=2){
csum=(csum*2-C(dn,dl)+C(dn,dr+1))%mod;
dn++, dl++, dr++;
csum=(csum*2+C(dn,dl-1)-C(dn,dr))%mod;
dn++;
res[i]+=op*csum;
}
}
{
int cle=(cx+1)&1, cri=(cx+1+n)%2? n-1: n-2;
int dn=1, dl=(cle-cx+1)/2, dr=(cri-cx+1)/2;
int csum=Sum(1, dl, dr);
res[1]+=op*csum;
for(int i=3;i<=d;i+=2){
csum=(csum*2-C(dn,dl)+C(dn,dr+1))%mod;
dn++, dl++, dr++;
csum=(csum*2+C(dn,dl-1)-C(dn,dr))%mod;
dn++;
res[i]+=op*csum;
}
}
};
calc(a,1);
int cx=a,op=1;
while(1){
if(op==1){
cx=-2-cx, op=-1;
}
else{
cx=n*2-cx, op=1;
}
if(abs(cx)>d && abs(cx-(n-1))>d){
break;
}
calc(cx,op);
}
cx=a, op=1;
while(1){
if(op==1){
cx=n*2-cx, op=-1;
}
else{
cx=-2-cx, op=1;
}
if(abs(cx)>d && abs(cx-(n-1))>d){
break;
}
calc(cx,op);
}
rep(i,0,d){
res[i]=(res[i]%mod+mod)*ifac[i]%mod;
}
return res;
}
}
int d,n,m,k,a,b,c;
signed main(){
// freopen("bacteria.in","r",stdin);
// freopen("bacteria.out","w",stdout);
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
init();
cin>>d>>n>>m>>k>>a>>b>>c;
solve(n,a-1,d);
vi X=solve(n,a-1,d), Y=solve(m,b-1,d), Z=solve(k,c-1,d);
X=mul(X,Y);
X.resize(d+1);
X=mul(X,Z);
X.resize(d+1);
int ans=X[d]*fac[d]%mod;
cout<<ans<<'\n';
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 5
Accepted
Test #1:
score: 5
Accepted
time: 32ms
memory: 15388kb
input:
50 41 46 42 8 20 21
output:
791406134
result:
ok 1 number(s): "791406134"
Test #2:
score: 0
Accepted
time: 36ms
memory: 15516kb
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: 33ms
memory: 15672kb
input:
5000 4994 4990 4990 976 2257 2505
output:
836390717
result:
ok 1 number(s): "836390717"
Test #4:
score: 0
Accepted
time: 36ms
memory: 15652kb
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: 89ms
memory: 19112kb
input:
120000 300 1 1 141 1 1
output:
637174
result:
ok 1 number(s): "637174"
Test #6:
score: 0
Accepted
time: 200ms
memory: 19136kb
input:
120000 994 1 1 15 1 1
output:
218803691
result:
ok 1 number(s): "218803691"
Test #7:
score: 0
Accepted
time: 41ms
memory: 19112kb
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: 48ms
memory: 19176kb
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: 91ms
memory: 19280kb
input:
120000 13997 13996 1 42 9266 1
output:
775637357
result:
ok 1 number(s): "775637357"
Test #10:
score: 0
Accepted
time: 96ms
memory: 19204kb
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: 119ms
memory: 19268kb
input:
120000 294 296 1 142 273 1
output:
889786082
result:
ok 1 number(s): "889786082"
Test #12:
score: 0
Accepted
time: 140ms
memory: 19128kb
input:
120000 395 390 1 370 185 1
output:
884557050
result:
ok 1 number(s): "884557050"
Test #13:
score: 0
Accepted
time: 170ms
memory: 19104kb
input:
120000 491 495 1 430 25 1
output:
272929924
result:
ok 1 number(s): "272929924"
Test #14:
score: 0
Accepted
time: 184ms
memory: 19104kb
input:
120000 590 593 1 418 459 1
output:
446962505
result:
ok 1 number(s): "446962505"
Test #15:
score: 0
Accepted
time: 211ms
memory: 19108kb
input:
120000 697 690 1 166 450 1
output:
216092107
result:
ok 1 number(s): "216092107"
Test #16:
score: 0
Accepted
time: 224ms
memory: 19140kb
input:
120000 793 799 1 416 61 1
output:
661260042
result:
ok 1 number(s): "661260042"
Test #17:
score: 0
Accepted
time: 287ms
memory: 19332kb
input:
120000 1000 1000 1 613 547 1
output:
429669083
result:
ok 1 number(s): "429669083"
Test #18:
score: 0
Accepted
time: 421ms
memory: 19296kb
input:
120000 1993 1995 1 493 565 1
output:
609392900
result:
ok 1 number(s): "609392900"
Test #19:
score: 0
Accepted
time: 193ms
memory: 19148kb
input:
120000 4995 4998 1 3166 3765 1
output:
394497547
result:
ok 1 number(s): "394497547"
Test #20:
score: 0
Accepted
time: 114ms
memory: 19128kb
input:
120000 9994 9991 1 6099 691 1
output:
795651799
result:
ok 1 number(s): "795651799"
Test #21:
score: 0
Accepted
time: 48ms
memory: 19148kb
input:
120000 49990 49990 1 41933 2862 1
output:
360787513
result:
ok 1 number(s): "360787513"
Test #22:
score: 0
Accepted
time: 39ms
memory: 19128kb
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: 141ms
memory: 19340kb
input:
120000 296 300 297 89 130 280
output:
702788425
result:
ok 1 number(s): "702788425"
Test #24:
score: 0
Accepted
time: 169ms
memory: 19132kb
input:
120000 392 397 391 222 280 10
output:
322470184
result:
ok 1 number(s): "322470184"
Test #25:
score: 0
Accepted
time: 212ms
memory: 19116kb
input:
120000 499 498 500 263 315 367
output:
449848666
result:
ok 1 number(s): "449848666"
Test #26:
score: 0
Accepted
time: 247ms
memory: 19284kb
input:
120000 598 591 594 497 474 400
output:
35486519
result:
ok 1 number(s): "35486519"
Test #27:
score: 0
Accepted
time: 276ms
memory: 19288kb
input:
120000 694 692 695 625 173 477
output:
785203749
result:
ok 1 number(s): "785203749"
Test #28:
score: 0
Accepted
time: 306ms
memory: 19196kb
input:
120000 794 796 800 395 465 507
output:
897269426
result:
ok 1 number(s): "897269426"
Test #29:
score: 0
Accepted
time: 373ms
memory: 19116kb
input:
120000 993 998 991 196 712 911
output:
464727191
result:
ok 1 number(s): "464727191"
Test #30:
score: 0
Accepted
time: 547ms
memory: 19328kb
input:
120000 1991 2000 1994 1937 1362 1494
output:
473701811
result:
ok 1 number(s): "473701811"
Test #31:
score: 0
Accepted
time: 240ms
memory: 19148kb
input:
120000 4994 4990 4990 646 1214 2276
output:
763540821
result:
ok 1 number(s): "763540821"
Test #32:
score: 0
Accepted
time: 144ms
memory: 19124kb
input:
120000 9994 9992 9991 6588 9538 2632
output:
804858722
result:
ok 1 number(s): "804858722"
Test #33:
score: 0
Accepted
time: 47ms
memory: 19280kb
input:
120000 49997 49997 49993 46278 44140 26931
output:
139550295
result:
ok 1 number(s): "139550295"
Test #34:
score: 0
Accepted
time: 50ms
memory: 19144kb
input:
120000 119997 120000 120000 24867 116477 35338
output:
946147605
result:
ok 1 number(s): "946147605"