QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#294191 | #4903. 细菌 | Bronya | 15 | 175ms | 16604kb | C++14 | 3.5kb | 2023-12-30 09:42:07 | 2023-12-30 09:42:08 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int mo=998244353,G=3;
const int N=1000000;
int fact[N+5],ifact[N+5];
int fast_pow(int a,int p){
int sum=1;
while(p){
if(p&1)sum=1ll*a*sum%mo;
a=1ll*a*a%mo;
p>>=1;
}
return sum;
}
const int invG=fast_pow(G,mo-2);
int rev[4000005];
int add(int u,int v){
return (u+v>=mo?u+v-mo:u+v);
}
int C(int u,int v){
if(u<v)return 0;
return 1ll*fact[u]*ifact[v]%mo*1ll*ifact[u-v]%mo;
}
void Init(){
fact[0]=1;
for(int i=1;i<=N;i++)fact[i]=1ll*fact[i-1]*i%mo;
ifact[N]=fast_pow(fact[N],mo-2);
for(int i=N-1;i>=0;i--)ifact[i]=ifact[i+1]*1ll*(i+1)%mo;
}
void NTT(int *A,int len,bool op){
for(int i=0;i<len;i++)rev[i]=(rev[i>>1]>>1)|(((i&1)?(len>>1):0));
for(int i=0;i<len;i++)
if(i<rev[i])swap(A[i],A[rev[i]]);
for(int i=2;i<=len;i*=2){
int now=i/2;
int buf=fast_pow((op?G:invG),(mo-1)/i);
for(int j=0;j<len;j+=i){
int pg=1;
for(int k=0;k<now;k++){
int x=A[j+k],y=A[j+k+now];
A[j+k]=add(x,1ll*y*pg%mo);
A[j+k+now]=add(x,mo-1ll*y*pg%mo);
pg=1ll*pg*buf%mo;
}
}
}
if(!op){
int invL=fast_pow(len,mo-2);
for(int i=0;i<len;i++)A[i]=1ll*A[i]*invL%mo;
}
}
void times(int *A,int *B,int n){
for(int i=0;i<n;i++)A[i]=1ll*A[i]*B[i]%mo;
}
void mul(int *A,int *B,int n,int lim){
int L=1;while(L<=2*n)L<<=1;
static int sav[4000005];
memcpy(sav,B,sizeof(int)*L);
NTT(A,L,1);NTT(B,L,1);
times(A,B,L);
NTT(A,L,0);
memset(A+lim,0,sizeof(int)*(L-lim));memset(sav,0,sizeof(int)*L);
}
namespace Subtaskk1{
int f[120005],g[120005];
void Solve(int *A,int d,int n,int x){
for(int i=0;i<=n+1;i++)f[i]=g[i]=0;
f[x]=1;A[0]=1;
for(int i=1;i<=d;i++){
for(int j=1;j<=n;j++)g[j]=add(f[j-1],f[j+1]);
for(int j=1;j<=n;j++){
f[j]=g[j];g[j]=0;
A[i]=add(A[i],f[j]);
}
}
}
}
namespace Subtaskk2{
int calc(int x,int y,int u,int v,int op){
if(x<0||y<0)return 0;
if(x==0&&y==0)return 1;
int sav=C(x+y,x);
swap(x,y);
if(!op)x-=u,y+=u;
else x-=v,y+=v;
return add(sav,mo-calc(x,y,u,v,op^1));
}
int calc2(int x,int y,int u,int v){
if(x==0&&y==0)return 1;
if(x<0||y<0||y-x>=u||y-x<=v)return 0;
return add(C(x+y,x),mo-add(calc(y-v,x+v,u,v,0),calc(y-u,x+u,u,v,1)));
}
void Solve(int *A,int d,int n,int x){
int u=x,v=-(n-x+1);A[0]=1;
for(int i=1;i<=d;i++){
A[i]=add(A[i-1],A[i-1]);
if((i-1-u)%2!=0)A[i]=add(A[i],mo-calc2((i-u)/2,i-1-(i-u)/2,u,v));
if((i-1-v)%2!=0)A[i]=add(A[i],mo-calc2((i-v-2)/2,i-1-(i-v-2)/2,u,v));
}
}
}
int main(){
static int X[4000005],Y[4000005],Z[4000005];
int d,n,m,k,a,b,c;Init();
scanf("%d%d%d%d%d%d%d",&d,&n,&m,&k,&a,&b,&c);
if(1ll*n*n<=d){
Subtaskk1::Solve(X,d,n,a);
Subtaskk1::Solve(Y,d,m,b);
Subtaskk1::Solve(Z,d,k,c);
}
else {
Subtaskk2::Solve(X,d,n,a);
Subtaskk2::Solve(Y,d,m,b);
Subtaskk2::Solve(Z,d,k,c);
}
for(int i=0;i<=d;i++){
X[i]=1ll*X[i]*ifact[i]%mo;
Y[i]=1ll*Y[i]*ifact[i]%mo;
Z[i]=1ll*Z[i]*ifact[i]%mo;
}
mul(X,Y,d+1,d+1);mul(X,Z,d+1,d+1);
printf("%d\n",1ll*X[d]*fact[d]%mo);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 5
Accepted
Test #1:
score: 5
Accepted
time: 8ms
memory: 11464kb
input:
50 41 46 42 8 20 21
output:
791406134
result:
ok 1 number(s): "791406134"
Test #2:
score: 0
Accepted
time: 12ms
memory: 11708kb
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: 10ms
memory: 11800kb
input:
5000 4994 4990 4990 976 2257 2505
output:
836390717
result:
ok 1 number(s): "836390717"
Test #4:
score: 0
Accepted
time: 16ms
memory: 11744kb
input:
5000 4994 4997 4994 4399 1826 1332
output:
65414465
result:
ok 1 number(s): "65414465"
Subtask #3:
score: 0
Time Limit Exceeded
Test #5:
score: 15
Accepted
time: 175ms
memory: 16604kb
input:
120000 300 1 1 141 1 1
output:
637174
result:
ok 1 number(s): "637174"
Test #6:
score: -15
Time Limit Exceeded
input:
120000 994 1 1 15 1 1
output:
result:
Subtask #4:
score: 0
Time Limit Exceeded
Test #8:
score: 0
Time Limit Exceeded
input:
119000 119991 119991 1 23819 52139 1
output:
result:
Subtask #5:
score: 0
Skipped
Dependency #4:
0%
Subtask #6:
score: 0
Skipped
Dependency #3:
0%
Subtask #7:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
0%