QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#400681 | #4903. 细菌 | Iratis | 55 | 739ms | 60716kb | C++20 | 4.0kb | 2024-04-27 15:04:56 | 2024-04-27 15:04:56 |
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)+5;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)+5;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<=sqrt(Day))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: 4ms
memory: 39300kb
input:
50 41 46 42 8 20 21
output:
791406134
result:
ok 1 number(s): "791406134"
Test #2:
score: 0
Accepted
time: 8ms
memory: 39436kb
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: 38348kb
input:
5000 4994 4990 4990 976 2257 2505
output:
836390717
result:
ok 1 number(s): "836390717"
Test #4:
score: 0
Accepted
time: 12ms
memory: 39988kb
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: 211ms
memory: 56592kb
input:
120000 300 1 1 141 1 1
output:
637174
result:
ok 1 number(s): "637174"
Test #6:
score: 0
Accepted
time: 739ms
memory: 56292kb
input:
120000 994 1 1 15 1 1
output:
218803691
result:
ok 1 number(s): "218803691"
Test #7:
score: 0
Accepted
time: 79ms
memory: 60716kb
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: 86ms
memory: 57944kb
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: 172ms
memory: 54288kb
input:
120000 13997 13996 1 42 9266 1
output:
775637357
result:
ok 1 number(s): "775637357"
Test #10:
score: 0
Accepted
time: 183ms
memory: 54172kb
input:
120000 13997 13997 1 9768 6131 1
output:
151873213
result:
ok 1 number(s): "151873213"
Subtask #6:
score: 0
Time Limit Exceeded
Dependency #3:
100%
Accepted
Dependency #5:
100%
Accepted
Test #11:
score: 35
Accepted
time: 352ms
memory: 58972kb
input:
120000 294 296 1 142 273 1
output:
889786082
result:
ok 1 number(s): "889786082"
Test #12:
score: -35
Time Limit Exceeded
input:
120000 395 390 1 370 185 1
output:
result:
Subtask #7:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
100%
Accepted
Dependency #5:
100%
Accepted
Dependency #6:
0%