QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#91629#4903. 细菌Silver187100 ✓793ms86568kbC++145.6kb2023-03-29 10:37:012023-03-29 10:37:05

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-29 10:37:05]
  • 评测
  • 测评结果:100
  • 用时:793ms
  • 内存:86568kb
  • [2023-03-29 10:37:01]
  • 提交

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;
} 
/*
*/

詳細信息

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"