QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#400685 | #4903. 细菌 | Iratis | 90 | 1422ms | 61376kb | C++20 | 4.0kb | 2024-04-27 15:07:16 | 2024-04-27 15:07:17 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define md(a) a=(a%mod+mod)%mod
#define file(a) freopen(#a".in","r",stdin);freopen(#a".out","w",stdout)
bool ST;
const int N=1000005,mod=998244353;
namespace Math
{
int fac[N],inv[N],upd,iv[N];
inline void add(int &x,const int &y){x+=y;if(x>=mod)x-=mod;}
inline void dec(int &x,const int &y){x-=y;if(x<0)x+=mod;}
inline int qp(int a,int n){int b=1;while(n){if(n&1)b=b*a%mod;a=a*a%mod,n>>=1;}return b;}
inline void PreC()
{
upd=N-5,fac[0]=1;for(int i=1;i<=upd;i++)fac[i]=fac[i-1]*i%mod;
inv[upd]=qp(fac[upd],mod-2);for(int i=upd-1;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod;
for(int i=1;i<=upd;i++)iv[i]=inv[i]*fac[i-1]%mod;
}
inline int C(int n,int m){if(n<m||m<0)return 0;return fac[n]*inv[m]%mod*inv[n-m]%mod;}
};
using namespace Math;
int Day,n,m,h,qx,qy,qz,X[N],Y[N],Z[N];
namespace Force
{
int dp[N],tmp[N];int *f;int *g;
inline void main(int p,int q,int *Val)
{
f=dp+n,g=tmp+n;for(int i=-p;i<=q;i++)f[i]=0;f[0]=1;Val[0]=1;
for(int d=1;d<=Day;d++)
{
for(int i=-p;i<=q;i++)g[i]=f[i],f[i]=0;
for(int i=-p;i<=q;i++){if(i-1>=-p)add(f[i-1],g[i]);if(i+1<=q)add(f[i+1],g[i]);}
for(int i=-p;i<=q;i++)add(Val[d],f[i]);
}
}
};
inline void Rev(int &x,int &y,int p){x+=p,y-=p;swap(x,y);}
namespace Right
{
int P,Q;
inline void Push(int &val,int l,int r,int d)
{
val=val*2%mod;dec(val,C(d,l)),add(val,C(d,r+1));
val=val*2%mod;dec(val,C(d+1,r+1)),add(val,C(d+1,l));
}
inline void Start(int x,int y,int tag,int *f)
{
// cout<<x<<" "<<y<<endl;
int l,r,val;
l=ceil((-P)/2.0)-x,r=floor(Q/2.0)-x,val=0;for(int i=0;i<=0;i++)if(l<=i&&i<=r)add(val,C(0,i));
for(int d=0;d<=Day;d+=2)add(f[d],val*tag%mod),Push(val,l,r,d),l++,r++;
l=ceil((1-P)/2.0)-x,r=floor((1+Q)/2.0)-x,val=0;for(int i=0;i<=1;i++)if(l<=i&&i<=r)add(val,C(1,i));
for(int d=1;d<=Day;d+=2)add(f[d],val*tag%mod),Push(val,l,r,d),l++,r++;
}
inline void main(int p,int q,int *f)
{
P=p,Q=q,p++,q++;int x=0,y=0;Start(x,y,1,f);
x=y=0;for(int t=1;t<=Day/(p+q)+2;t++){if(t&1)Rev(x,y,p);else Rev(x,y,-q);Start(x,y,(t&1)?mod-1:1,f);}
x=y=0;for(int t=1;t<=Day/(p+q)+2;t++){if(t&1)Rev(x,y,-q);else Rev(x,y,p);Start(x,y,(t&1)?mod-1:1,f);}
}
};
namespace Iratis
{
inline void main(int p,int q,int *Val)
{
// Force::main(p,q,Val);return ;
// Right::main(p,q,Val);return ;
if(p+q+1<=800)Force::main(p,q,Val);
else Right::main(p,q,Val);
}
};
namespace cul8r
{
int lim,l,A[N],B[N],rev[N],ome[N],va[N],vb[N];
inline void NTT(int *A,int type)
{
for(int i=0;i<lim;i++)if(i<rev[i])swap(A[i],A[rev[i]]);
for(int p=1;p<=l;p++)
{
int m=(1<<p),wm=qp(3,(mod-1)/m);if(type==-1)wm=qp(wm,mod-2);
ome[0]=1;for(int j=1;j<m/2;j++)ome[j]=1ll*ome[j-1]*wm%mod;
for(int i=0;i<lim;i+=m)for(int j=0;j<m/2;j++)
{
int u=A[i+j],t=1ll*ome[j]*A[i+j+m/2]%mod,v=u-t;u+=t;
if(u>=mod)u-=mod;if(v<0)v+=mod;A[i+j]=u,A[i+j+m/2]=v;
}
}
}
inline void Merge(int n,int m)
{
lim=1,l=0;while(lim<=n+m)lim<<=1,l++;
for(int i=0;i<lim;i++)rev[i]=((rev[i>>1]>>1)|((i&1)<<(l-1))),A[i]=B[i]=0;
for(int i=0;i<=n;i++)A[i]=va[i];for(int i=0;i<=m;i++)B[i]=vb[i];
NTT(A,1),NTT(B,1);for(int i=0;i<lim;i++)A[i]=1ll*A[i]*B[i]%mod;int P=qp(lim,mod-2);
NTT(A,-1);for(int i=0;i<lim;i++)A[i]=1ll*A[i]*P%mod;for(int i=0;i<=n+m;i++)va[i]=A[i];
}
inline void solve()
{
// for(int i=0;i<=Day;i++)cerr<<X[i]<<' ';cout<<'\n';
// for(int i=0;i<=Day;i++)cerr<<Y[i]<<' ';cout<<'\n';
// for(int i=0;i<=Day;i++)cerr<<Z[i]<<' ';cout<<'\n';
for(int i=0;i<=Day;i++)va[i]=X[i]*inv[i]%mod,vb[i]=Y[i]*inv[i]%mod;Merge(Day,Day);
for(int i=0;i<=Day;i++)vb[i]=Z[i]*inv[i]%mod;Merge(Day,Day);cout<<va[Day]*fac[Day]%mod<<'\n';
}
};
bool ED;
signed main()
{
int time_st=clock();
cerr<<(&ST-&ED)/1024.0/1024<<endl;ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>Day>>n>>m>>h>>qx>>qy>>qz;PreC();
Iratis::main(qx-1,n-qx,X),Iratis::main(qy-1,m-qy,Y),Iratis::main(qz-1,h-qz,Z);
cul8r::solve();cerr<<(clock()-time_st)/1e6<<endl;return 0;
}
詳細信息
Subtask #1:
score: 5
Accepted
Test #1:
score: 5
Accepted
time: 3ms
memory: 47284kb
input:
50 41 46 42 8 20 21
output:
791406134
result:
ok 1 number(s): "791406134"
Test #2:
score: 0
Accepted
time: 18ms
memory: 46580kb
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: 11ms
memory: 37996kb
input:
5000 4994 4990 4990 976 2257 2505
output:
836390717
result:
ok 1 number(s): "836390717"
Test #4:
score: 0
Accepted
time: 8ms
memory: 40880kb
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: 203ms
memory: 58388kb
input:
120000 300 1 1 141 1 1
output:
637174
result:
ok 1 number(s): "637174"
Test #6:
score: 0
Accepted
time: 742ms
memory: 56184kb
input:
120000 994 1 1 15 1 1
output:
218803691
result:
ok 1 number(s): "218803691"
Test #7:
score: 0
Accepted
time: 69ms
memory: 55316kb
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: 79ms
memory: 53812kb
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: 160ms
memory: 56540kb
input:
120000 13997 13996 1 42 9266 1
output:
775637357
result:
ok 1 number(s): "775637357"
Test #10:
score: 0
Accepted
time: 163ms
memory: 55952kb
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: 356ms
memory: 61260kb
input:
120000 294 296 1 142 273 1
output:
889786082
result:
ok 1 number(s): "889786082"
Test #12:
score: 0
Accepted
time: 441ms
memory: 60244kb
input:
120000 395 390 1 370 185 1
output:
884557050
result:
ok 1 number(s): "884557050"
Test #13:
score: 0
Accepted
time: 555ms
memory: 58240kb
input:
120000 491 495 1 430 25 1
output:
272929924
result:
ok 1 number(s): "272929924"
Test #14:
score: 0
Accepted
time: 651ms
memory: 61376kb
input:
120000 590 593 1 418 459 1
output:
446962505
result:
ok 1 number(s): "446962505"
Test #15:
score: 0
Accepted
time: 742ms
memory: 56608kb
input:
120000 697 690 1 166 450 1
output:
216092107
result:
ok 1 number(s): "216092107"
Test #16:
score: 0
Accepted
time: 843ms
memory: 61144kb
input:
120000 793 799 1 416 61 1
output:
661260042
result:
ok 1 number(s): "661260042"
Test #17:
score: 0
Accepted
time: 1422ms
memory: 56388kb
input:
120000 1000 1000 1 613 547 1
output:
429669083
result:
ok 1 number(s): "429669083"
Test #18:
score: 0
Accepted
time: 747ms
memory: 56512kb
input:
120000 1993 1995 1 493 565 1
output:
609392900
result:
ok 1 number(s): "609392900"
Test #19:
score: 0
Accepted
time: 334ms
memory: 54652kb
input:
120000 4995 4998 1 3166 3765 1
output:
394497547
result:
ok 1 number(s): "394497547"
Test #20:
score: 0
Accepted
time: 207ms
memory: 54588kb
input:
120000 9994 9991 1 6099 691 1
output:
795651799
result:
ok 1 number(s): "795651799"
Test #21:
score: 0
Accepted
time: 95ms
memory: 57944kb
input:
120000 49990 49990 1 41933 2862 1
output:
360787513
result:
ok 1 number(s): "360787513"
Test #22:
score: 0
Accepted
time: 80ms
memory: 57740kb
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: 506ms
memory: 56424kb
input:
120000 296 300 297 89 130 280
output:
702788425
result:
ok 1 number(s): "702788425"
Test #24:
score: 0
Accepted
time: 641ms
memory: 61372kb
input:
120000 392 397 391 222 280 10
output:
322470184
result:
ok 1 number(s): "322470184"
Test #25:
score: 0
Accepted
time: 810ms
memory: 58800kb
input:
120000 499 498 500 263 315 367
output:
449848666
result:
ok 1 number(s): "449848666"
Test #26:
score: 0
Accepted
time: 949ms
memory: 57132kb
input:
120000 598 591 594 497 474 400
output:
35486519
result:
ok 1 number(s): "35486519"
Test #27:
score: 0
Accepted
time: 1088ms
memory: 56464kb
input:
120000 694 692 695 625 173 477
output:
785203749
result:
ok 1 number(s): "785203749"
Test #28:
score: 0
Accepted
time: 1244ms
memory: 58736kb
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
output:
464727191