QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#806770#7974. 染色JohnAlfnov100 ✓15ms13616kbC++141.1kb2024-12-09 14:59:562024-12-09 14:59:58

Judging History

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

  • [2024-12-09 14:59:58]
  • 评测
  • 测评结果:100
  • 用时:15ms
  • 内存:13616kb
  • [2024-12-09 14:59:56]
  • 提交

answer

#include<bits/stdc++.h>
#define mod 998244353
using namespace std;
int powdv(int x,int y=mod-2){
	int ans=1;
	while(y){
		if(y&1)ans=1ll*ans*x%mod;
		y>>=1,x=1ll*x*x%mod;
	}
	return ans;
}
int di[500005],id[500005];
inline int C(int n,int m){
	return 1ll*di[n]*id[m]%mod*id[n-m]%mod;
}
inline int CC(int n,int m){
	return 1ll*di[m]*di[n-m]%mod;
}
int A[500005],B[500005],an[500005];
int main(){
	int n,m,k;
	scanf("%d%d%d",&n,&m,&k);
	int N=n*m;
	di[0]=1;
	for(int i=1;i<=N;++i)di[i]=1ll*i*di[i-1]%mod;
	id[N]=powdv(di[N]);
	for(int i=N-1;i>=0;--i)id[i]=1ll*id[i+1]*(i+1)%mod;
	an[0]=1;an[1]=(N-2*k+mod)%mod;
	for(int n=1;n<N;++n){
		an[n+1]=(1ll*an[1]*an[n]+(n-N-1ll+mod)*an[n-1])%mod*di[n]%mod*id[n+1]%mod;
	}
	int C2=1ll*id[k]*id[N-k]%mod;
	for(int i=0;i<=N;++i)an[i]=1ll*CC(N,i)*an[i]%mod;
	for(int a=0;a<=n;++a)A[a]=a%2?mod-C(n,a):C(n,a);
	for(int b=0;b<=m;++b)B[b]=b%2?mod-C(m,b):C(m,b);
	int he=0;
	for(int a=0;a<=n;++a)for(int b=0;b<=m;++b){
		he=(he+1ll*A[a]*B[b]%mod*an[a*(m-b)+b*(n-a)])%mod;
	}
	int ans=1ll*he*C2%mod*powdv((mod+1)/2,n+m)%mod;
	printf("%d\n",ans);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Pretests


Final Tests

Test #1:

score: 5
Accepted
time: 1ms
memory: 10036kb

input:

3 5 7

output:

105

result:

ok single line: '105'

Test #2:

score: 5
Accepted
time: 0ms
memory: 11924kb

input:

4 4 8

output:

144

result:

ok single line: '144'

Test #3:

score: 5
Accepted
time: 2ms
memory: 11984kb

input:

9 7 53

output:

11271960

result:

ok single line: '11271960'

Test #4:

score: 5
Accepted
time: 0ms
memory: 11928kb

input:

10 10 60

output:

711797984

result:

ok single line: '711797984'

Test #5:

score: 5
Accepted
time: 2ms
memory: 11996kb

input:

50 100 100

output:

684521374

result:

ok single line: '684521374'

Test #6:

score: 5
Accepted
time: 0ms
memory: 9984kb

input:

69 69 99

output:

205514286

result:

ok single line: '205514286'

Test #7:

score: 5
Accepted
time: 0ms
memory: 9900kb

input:

500 10 3232

output:

571588252

result:

ok single line: '571588252'

Test #8:

score: 5
Accepted
time: 0ms
memory: 12072kb

input:

70 70 4800

output:

851456413

result:

ok single line: '851456413'

Test #9:

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

input:

100 1000 50000

output:

437541409

result:

ok single line: '437541409'

Test #10:

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

input:

316 316 4238

output:

753478761

result:

ok single line: '753478761'

Test #11:

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

input:

201 479 30001

output:

594408179

result:

ok single line: '594408179'

Test #12:

score: 5
Accepted
time: 12ms
memory: 13616kb

input:

706 706 706

output:

835727049

result:

ok single line: '835727049'

Test #13:

score: 5
Accepted
time: 15ms
memory: 13440kb

input:

2023 233 2023

output:

801992885

result:

ok single line: '801992885'

Test #14:

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

input:

402 402 1000

output:

940937548

result:

ok single line: '940937548'

Test #15:

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

input:

707 333 999

output:

732112489

result:

ok single line: '732112489'

Test #16:

score: 5
Accepted
time: 7ms
memory: 12448kb

input:

600 600 18000

output:

579276872

result:

ok single line: '579276872'

Test #17:

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

input:

389 1047 40001

output:

186903191

result:

ok single line: '186903191'

Test #18:

score: 5
Accepted
time: 7ms
memory: 13616kb

input:

707 707 42837

output:

468460621

result:

ok single line: '468460621'

Test #19:

score: 5
Accepted
time: 15ms
memory: 13500kb

input:

100 5000 32346

output:

460579847

result:

ok single line: '460579847'

Test #20:

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

input:

501 501 251001

output:

1

result:

ok single line: '1'