QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#91629 | #4903. 细菌 | Silver187 | 100 ✓ | 793ms | 86568kb | C++14 | 5.6kb | 2023-03-29 10:37:01 | 2023-03-29 10:37:05 |
Judging History
answer
#include <bits/stdc++.h>
#include <assert.h>
#include <unordered_set>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define LL long long
#define pp pair<LL,int>
#define mp make_pair
#define ull unsigned long long
namespace IO{
const int sz=1<<22;
char a[sz+5],b[sz+5],*p1=a,*p2=a,*t=b,p[105];
inline char gc(){
return getchar();
// return p1==p2?(p2=(p1=a)+fread(a,1,sz,stdin),p1==p2?EOF:*p1++):*p1++;
}
template<class T> void gi(T& x){
x=0; int f=1;char c=gc();
if(c=='-')f=-1;
for(;c<'0'||c>'9';c=gc())if(c=='-')f=-1;
for(;c>='0'&&c<='9';c=gc())
x=x*10+(c-'0');
x=x*f;
}
inline void flush(){fwrite(b,1,t-b,stdout),t=b; }
inline void pc(char x){*t++=x; if(t-b==sz) flush(); }
template<class T> void pi(T x,char c='\n'){
if(x<0)pc('-'),x=-x;
if(x==0) pc('0'); int t=0;
for(;x;x/=10) p[++t]=x%10+'0';
for(;t;--t) pc(p[t]); pc(c);
}
struct F{~F(){flush();}}f;
}
using IO::gi;
using IO::pi;
using IO::pc;
using IO::gc;
const int mod=998244353;
const int inv2=(mod+1)>>1;
inline int add(int x,int y){
return x+y>=mod?x+y-mod:x+y;
}
inline int dec(int x,int y){
return x-y<0?x-y+mod:x-y;
}
inline int qkpow(int a,int b){
int ans=1,base=a;
while(b){
if(b&1)ans=1ll*ans*base%mod;
base=1ll*base*base%mod;
b>>=1;
}
return ans;
}
int fac[1000005],inv[1000005],Invn[1000005];
inline int binom(int n,LL m){
if(n<m||m<0)return 0;
return 1ll*fac[n]*inv[m]%mod*inv[n-m]%mod;
}
void init_C(int N){
fac[0]=1;
for(int i=1;i<=N;i++)fac[i]=1ll*fac[i-1]*i%mod;
inv[0]=1;
inv[N]=qkpow(fac[N],mod-2);
for(int i=N-1;i>=1;i--)inv[i]=1ll*inv[i+1]*(i+1)%mod;
Invn[0]=Invn[1]=1;
for(int i=2;i<=N;i++)Invn[i]=1ll*inv[i]*fac[i-1]%mod;
}
const int MAXN=6e5+5;
int rev[MAXN],F[MAXN],Q[MAXN],W[23][MAXN<<1],f[MAXN],g[MAXN];
inline int mul(int a,int b){return 1ll*a*b%mod;}
void init(){
int wn;
for(int i=0,x=1;x<MAXN;i++,x<<=1){
W[i][x]=1;
wn=qkpow(3,(mod-1)/(x<<1));
for(int j=1;j<x;j++)W[i][x+j]=1ll*wn*W[i][x+j-1]%mod;
wn=qkpow(wn,mod-2);
for(int j=1;j<x;j++)W[i][x-j]=1ll*wn*W[i][x-j+1]%mod;
}
}
inline void NTT(int *a,int type,int n){
for(int i=0;i<n;i++)if(i<rev[i])swap(a[i],a[rev[i]]);
LL x,y;
for(int i=1,cnt=0;i<n;cnt++,i<<=1){
for(int j=0;j<n;j+=(i<<1)){
for(int t=0,k=j;k<j+i;k++,t+=type){
x=a[k],y=1ll*W[cnt][i+t]*a[k+i];
a[k]=(x+y)%mod;
a[k+i]=(x-y)%mod;
}
}
}
if(type==-1)for(int i=0;i<n;i++)a[i]=mul(a[i],Invn[n]);
}
void Polyinv(int *a,int *b,int len){
static int c[MAXN];
if(len==1){
b[0]=qkpow(a[0],mod-2);
return ;
}
Polyinv(a,b,(len+1)>>1);
int l=0,m=(len<<1),n=1;
for(;n<=m;n<<=1,l++);
for(int i=0;i<n;i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));
for(int i=0;i<len;i++)c[i]=a[i];
for(int i=len;i<n;i++)c[i]=0;
NTT(c,1,n),NTT(b,1,n);
for(int i=0;i<n;i++)b[i]=1ll*(2-1ll*b[i]*c[i])%mod*b[i]%mod;
NTT(b,-1,n);
for(int i=len;i<n;i++)b[i]=0;
}
inline int init_NTT(int L){
int l=0,m=L,n=1;
for(;n<=m;n<<=1,l++);
for(int i=0;i<n;i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));
return n;
}
void MUL(int *a,int *b,int *c,int n,int m,int lim){
static int t1[MAXN],t2[MAXN],t3[MAXN];
for(int i=0;i<n;i++)t1[i]=a[i];
for(int i=0;i<m;i++)t2[i]=b[i];
for(int i=n;i<lim;i++)t1[i]=0;
for(int i=m;i<lim;i++)t2[i]=0;
NTT(t1,1,lim),NTT(t2,1,lim);
for(int i=0;i<lim;i++)t3[i]=1ll*t1[i]*t2[i]%mod;
NTT(t3,-1,lim);
for(int i=0;i<n+m-1;i++)c[i]=(t3[i]%mod+mod)%mod;
}
int d,n,m,k,A,B,C,f1[MAXN],f2[MAXN],f3[MAXN],dp[120005],tmp[120005],k1,k2;
inline int calc2(int a,int b){
//从 (0,0)-->(a,b) 无限制的方案数
if((a+b)&1)return 0;
return binom(a,(a+b)>>1);
}
inline int calcf(int a,int b);
inline int calcg(int a,int b);
inline int calcf(int a,int b){//先接触 y=k1
if(a<abs(k1)+abs(b-k1))return 0;
return dec(calc2(a,b),calcg(a,2*k2-b));
}
inline int calcg(int a,int b){//先接触 y=k2
if(a<abs(k2)+abs(b-k2))return 0;
return dec(calc2(a,b),calcf(a,2*k1-b));
}
inline int solve(int a,int b,int K1,int K2){//(0,0)-->不接触 y=k1,y=k2;
k1=K1,k2=K2;
return dec(calc2(a,b),add(calcf(a,2*k1-b),calcg(a,2*k2-b)));
}
inline void calc(int *Ans,int st,int ban){
//只能在 [0,ban] 里面走
//起点为 [0,st]
if(ban<=400){
for(int i=0;i<=ban;i++)dp[i]=tmp[i]=0;
dp[st]=1;
Ans[0]=1;
for(int i=1;i<=d;i++){
for(int j=0;j<=ban;j++){
if(j-1>=0)tmp[j-1]=add(tmp[j-1],dp[j]);
if(j+1<=ban)tmp[j+1]=add(tmp[j+1],dp[j]);
}
for(int j=0;j<=ban;j++){
dp[j]=tmp[j],tmp[j]=0;
Ans[i]=add(Ans[i],dp[j]);
}
}
}else{
Ans[0]=1;
if(ban==0){
for(int i=1;i<=d;i++)Ans[i]=1;
return ;
}
for(int i=1;i<=d;i++){
int res=Ans[i-1];
//(0,st)->(i-1,0)
//(0,st)->(i-1,ban)
int s1=solve(i-1,-st,-1-st,ban+1-st),s2=solve(i-1,ban-st,-1-st,ban+1-st);
res=dec(res,add(s1,s2));
Ans[i]=add(1ll*res*2%mod,add(s1,s2));
}
}
}
signed main(){
init_C(1000000);
init();
gi(d),gi(n),gi(m),gi(k),gi(A),gi(B),gi(C);
n--,m--,k--,A--,B--,C--;
calc(f1,A,n);
calc(f2,B,m);
calc(f3,C,k);
for(int i=0;i<=d;i++){
f1[i]=1ll*f1[i]*inv[i]%mod;
f2[i]=1ll*f2[i]*inv[i]%mod;
f3[i]=1ll*f3[i]*inv[i]%mod;
}
int lim=init_NTT(2*d+2);
MUL(f1,f2,f1,d+1,d+1,lim);
MUL(f1,f3,f1,d+1,d+1,lim);
pi(1ll*f1[d]*fac[d]%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: 16ms
memory: 77148kb
input:
50 41 46 42 8 20 21
output:
791406134
result:
ok 1 number(s): "791406134"
Test #2:
score: 0
Accepted
time: 26ms
memory: 77316kb
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: 26ms
memory: 79316kb
input:
5000 4994 4990 4990 976 2257 2505
output:
836390717
result:
ok 1 number(s): "836390717"
Test #4:
score: 0
Accepted
time: 32ms
memory: 77272kb
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: 179ms
memory: 82564kb
input:
120000 300 1 1 141 1 1
output:
637174
result:
ok 1 number(s): "637174"
Test #6:
score: 0
Accepted
time: 178ms
memory: 80732kb
input:
120000 994 1 1 15 1 1
output:
218803691
result:
ok 1 number(s): "218803691"
Test #7:
score: 0
Accepted
time: 58ms
memory: 82308kb
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: 62ms
memory: 84868kb
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: 80ms
memory: 83860kb
input:
120000 13997 13996 1 42 9266 1
output:
775637357
result:
ok 1 number(s): "775637357"
Test #10:
score: 0
Accepted
time: 76ms
memory: 82300kb
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: 303ms
memory: 85732kb
input:
120000 294 296 1 142 273 1
output:
889786082
result:
ok 1 number(s): "889786082"
Test #12:
score: 0
Accepted
time: 401ms
memory: 81376kb
input:
120000 395 390 1 370 185 1
output:
884557050
result:
ok 1 number(s): "884557050"
Test #13:
score: 0
Accepted
time: 555ms
memory: 83460kb
input:
120000 491 495 1 430 25 1
output:
272929924
result:
ok 1 number(s): "272929924"
Test #14:
score: 0
Accepted
time: 450ms
memory: 83452kb
input:
120000 590 593 1 418 459 1
output:
446962505
result:
ok 1 number(s): "446962505"
Test #15:
score: 0
Accepted
time: 396ms
memory: 83364kb
input:
120000 697 690 1 166 450 1
output:
216092107
result:
ok 1 number(s): "216092107"
Test #16:
score: 0
Accepted
time: 359ms
memory: 83748kb
input:
120000 793 799 1 416 61 1
output:
661260042
result:
ok 1 number(s): "661260042"
Test #17:
score: 0
Accepted
time: 312ms
memory: 82732kb
input:
120000 1000 1000 1 613 547 1
output:
429669083
result:
ok 1 number(s): "429669083"
Test #18:
score: 0
Accepted
time: 178ms
memory: 84036kb
input:
120000 1993 1995 1 493 565 1
output:
609392900
result:
ok 1 number(s): "609392900"
Test #19:
score: 0
Accepted
time: 115ms
memory: 82940kb
input:
120000 4995 4998 1 3166 3765 1
output:
394497547
result:
ok 1 number(s): "394497547"
Test #20:
score: 0
Accepted
time: 79ms
memory: 80740kb
input:
120000 9994 9991 1 6099 691 1
output:
795651799
result:
ok 1 number(s): "795651799"
Test #21:
score: 0
Accepted
time: 61ms
memory: 82468kb
input:
120000 49990 49990 1 41933 2862 1
output:
360787513
result:
ok 1 number(s): "360787513"
Test #22:
score: 0
Accepted
time: 69ms
memory: 83584kb
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: 422ms
memory: 81012kb
input:
120000 296 300 297 89 130 280
output:
702788425
result:
ok 1 number(s): "702788425"
Test #24:
score: 0
Accepted
time: 537ms
memory: 83444kb
input:
120000 392 397 391 222 280 10
output:
322470184
result:
ok 1 number(s): "322470184"
Test #25:
score: 0
Accepted
time: 793ms
memory: 82784kb
input:
120000 499 498 500 263 315 367
output:
449848666
result:
ok 1 number(s): "449848666"
Test #26:
score: 0
Accepted
time: 655ms
memory: 82776kb
input:
120000 598 591 594 497 474 400
output:
35486519
result:
ok 1 number(s): "35486519"
Test #27:
score: 0
Accepted
time: 582ms
memory: 83776kb
input:
120000 694 692 695 625 173 477
output:
785203749
result:
ok 1 number(s): "785203749"
Test #28:
score: 0
Accepted
time: 512ms
memory: 82772kb
input:
120000 794 796 800 395 465 507
output:
897269426
result:
ok 1 number(s): "897269426"
Test #29:
score: 0
Accepted
time: 419ms
memory: 83708kb
input:
120000 993 998 991 196 712 911
output:
464727191
result:
ok 1 number(s): "464727191"
Test #30:
score: 0
Accepted
time: 227ms
memory: 82300kb
input:
120000 1991 2000 1994 1937 1362 1494
output:
473701811
result:
ok 1 number(s): "473701811"
Test #31:
score: 0
Accepted
time: 136ms
memory: 80896kb
input:
120000 4994 4990 4990 646 1214 2276
output:
763540821
result:
ok 1 number(s): "763540821"
Test #32:
score: 0
Accepted
time: 99ms
memory: 80728kb
input:
120000 9994 9992 9991 6588 9538 2632
output:
804858722
result:
ok 1 number(s): "804858722"
Test #33:
score: 0
Accepted
time: 66ms
memory: 83976kb
input:
120000 49997 49997 49993 46278 44140 26931
output:
139550295
result:
ok 1 number(s): "139550295"
Test #34:
score: 0
Accepted
time: 71ms
memory: 86568kb
input:
120000 119997 120000 120000 24867 116477 35338
output:
946147605
result:
ok 1 number(s): "946147605"