QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#359520#7974. 染色C1942huangjiaxu100 ✓46ms16264kbC++141.7kb2024-03-20 18:47:422024-03-20 18:47:42

Judging History

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

  • [2024-03-20 18:47:42]
  • 评测
  • 测评结果:100
  • 用时:46ms
  • 内存:16264kb
  • [2024-03-20 18:47:42]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=1<<19,P=998244353;
int n,m,t,k,fac[N],inv[N],f[N],w[N],A[N],B[N],lim,ans;
int ksm(int x,int y){
	int res=1;
	for(;y;y>>=1,x=1ll*x*x%P)if(y&1)res=1ll*res*x%P;
	return res;
}
void up(int n){
	lim=1;
	while(lim<=n)lim<<=1;
}
int C(int n,int m){
	return 1ll*fac[n]*inv[m]%P*inv[n-m]%P;
}
void init(){
	fac[0]=inv[0]=fac[1]=inv[1]=1;
	for(int i=2;i<N;++i)fac[i]=1ll*fac[i-1]*i%P,inv[i]=1ll*(P-P/i)*inv[P%i]%P;
	for(int i=2;i<N;++i)inv[i]=1ll*inv[i-1]*inv[i]%P;
	for(int mid=1,j,o;mid<N;mid<<=1)
		for(w[j=mid]=1,o=ksm(3,(P-1)/(mid<<1)),++j;j<mid<<1;++j)w[j]=1ll*w[j-1]*o%P;
	t=n*m,up(t);
}
inline int md(int x){
	return x>=P?x-P:x;
}
void DFT(int *A){
	for(int mid=lim>>1,j,k,*W,*a,*b,Y,R;mid;mid>>=1)
		for(j=0,R=mid<<1;j<lim;j+=R)
		 	for(k=0,W=w+mid,a=A+j,b=a+mid;k<mid;++k,++W,++a,++b)
				*b=1ll*md(*a+P-(Y=*b))**W%P,*a=md(*a+Y);
}
void IDFT(int *A){
	for(int mid=1,j,k,*W,*a,*b,Y,R;mid<lim;mid<<=1)
		for(j=0,R=mid<<1;j<lim;j+=R)
			for(k=0,W=w+mid,a=A+j,b=a+mid;k<mid;++k,++W,++a,++b)
				Y=1ll**b**W%P,*b=md(*a+P-Y),*a=md(*a+Y);
	reverse(A+1,A+lim);
	for(int in=ksm(lim,P-2),i=0;i<lim;++i)A[i]=1ll*A[i]*in%P;
}
int main(){
	scanf("%d%d%d",&n,&m,&k);
	init();
	for(int i=0;i<=k;++i)A[i]=md(1ll*(i&1?-1:1)*inv[i]*inv[k-i]%P+P);
	for(int i=0;i<=t-k;++i)B[i]=1ll*inv[i]*inv[t-k-i]%P;
	DFT(A),DFT(B);
	for(int i=0;i<lim;++i)A[i]=1ll*A[i]*B[i]%P;
	IDFT(A);
	for(int i=0;i<=t;++i)f[i]=1ll*A[i]*fac[i]%P*fac[t-i]%P;
	for(int i=0;i<=n;++i)for(int j=0;j<=m;++j)
		ans=(ans+1ll*(i+j&1?-1:1)*C(n,i)*C(m,j)%P*f[i*(m-j)+j*(n-i)])%P;
	ans=1ll*ans*ksm(P+1>>1,n+m)%P;
	printf("%d\n",md(ans+P));
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 5
Accepted
time: 5ms
memory: 14340kb

input:

3 5 7

output:

105

result:

ok single line: '105'

Test #2:

score: 5
Accepted
time: 6ms
memory: 14936kb

input:

4 4 8

output:

144

result:

ok single line: '144'

Test #3:

score: 5
Accepted
time: 8ms
memory: 14692kb

input:

9 7 53

output:

11271960

result:

ok single line: '11271960'

Test #4:

score: 5
Accepted
time: 8ms
memory: 14700kb

input:

10 10 60

output:

711797984

result:

ok single line: '711797984'

Test #5:

score: 5
Accepted
time: 4ms
memory: 15032kb

input:

50 100 100

output:

684521374

result:

ok single line: '684521374'

Test #6:

score: 5
Accepted
time: 9ms
memory: 14572kb

input:

69 69 99

output:

205514286

result:

ok single line: '205514286'

Test #7:

score: 5
Accepted
time: 5ms
memory: 15584kb

input:

500 10 3232

output:

571588252

result:

ok single line: '571588252'

Test #8:

score: 5
Accepted
time: 9ms
memory: 15656kb

input:

70 70 4800

output:

851456413

result:

ok single line: '851456413'

Test #9:

score: 5
Accepted
time: 16ms
memory: 14876kb

input:

100 1000 50000

output:

437541409

result:

ok single line: '437541409'

Test #10:

score: 5
Accepted
time: 16ms
memory: 15324kb

input:

316 316 4238

output:

753478761

result:

ok single line: '753478761'

Test #11:

score: 5
Accepted
time: 13ms
memory: 16072kb

input:

201 479 30001

output:

594408179

result:

ok single line: '594408179'

Test #12:

score: 5
Accepted
time: 46ms
memory: 16264kb

input:

706 706 706

output:

835727049

result:

ok single line: '835727049'

Test #13:

score: 5
Accepted
time: 46ms
memory: 16212kb

input:

2023 233 2023

output:

801992885

result:

ok single line: '801992885'

Test #14:

score: 5
Accepted
time: 25ms
memory: 16264kb

input:

402 402 1000

output:

940937548

result:

ok single line: '940937548'

Test #15:

score: 5
Accepted
time: 21ms
memory: 15264kb

input:

707 333 999

output:

732112489

result:

ok single line: '732112489'

Test #16:

score: 5
Accepted
time: 45ms
memory: 16196kb

input:

600 600 18000

output:

579276872

result:

ok single line: '579276872'

Test #17:

score: 5
Accepted
time: 45ms
memory: 16132kb

input:

389 1047 40001

output:

186903191

result:

ok single line: '186903191'

Test #18:

score: 5
Accepted
time: 46ms
memory: 16200kb

input:

707 707 42837

output:

468460621

result:

ok single line: '468460621'

Test #19:

score: 5
Accepted
time: 39ms
memory: 16220kb

input:

100 5000 32346

output:

460579847

result:

ok single line: '460579847'

Test #20:

score: 5
Accepted
time: 27ms
memory: 16216kb

input:

501 501 251001

output:

1

result:

ok single line: '1'