QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#288206#7974. 染色grass8cow100 ✓204ms36664kbC++171.8kb2023-12-22 10:40:592023-12-22 10:41:00

Judging History

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

  • [2023-12-22 10:41:00]
  • 评测
  • 测评结果:100
  • 用时:204ms
  • 内存:36664kb
  • [2023-12-22 10:40:59]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
int n,m,K;
const int mod=998244353,N=(1<<20),inv2=(mod+1)/2,G=3,GI=(mod+1)/3;
int qpow(int a,int b){
	int c=1;
	for(;b;b>>=1){
		if(b&1)c=1ll*a*c%mod;
		a=1ll*a*a%mod;
	}
	return c;
}
int jc[N+10],ij[N+10],p2[N+10],i2[N+10];
int C(int a,int b){
	if(a<b||a<0||b<0)return 0;
	return 1ll*jc[a]*ij[b]%mod*ij[a-b]%mod;
}
int lb[N],L;
void init(int n){
	L=1;while(L<=n)L<<=1;
	for(int i=0;i<L;i++)lb[i]=(lb[i>>1]>>1)|((i&1)?(L>>1):0);
}
void NTT(int *a,int fl){
	for(int i=0;i<L;i++)if(i>lb[i])swap(a[i],a[lb[i]]);
	for(int o=1;o<L;o<<=1){
		int Wn=qpow(fl?G:GI,(mod-1)/(o<<1));
		for(int i=0;i<L;i+=(o<<1))for(int j=0,w=1;j<o;j++,w=1ll*w*Wn%mod){
			int x=a[i+j],y=1ll*w*a[i+j+o]%mod;
			a[i+j]=(x+y)%mod,a[i+j+o]=(x-y)%mod;
		}
	}
	if(!fl){
		int I=qpow(L,mod-2);
		for(int i=0;i<L;i++)a[i]=1ll*a[i]*I%mod;
	}
} 
void sieve(){
	jc[0]=p2[0]=i2[0]=1;
	for(int i=1;i<=N;i++)p2[i]=2*p2[i-1]%mod,i2[i]=1ll*inv2*i2[i-1]%mod,
	jc[i]=1ll*i*jc[i-1]%mod;
	ij[N]=qpow(jc[N],mod-2);
	for(int i=N;i;i--)ij[i-1]=1ll*i*ij[i]%mod;
}
int fp[N+10],g[N+10],f[N+10];
int main(){
	sieve();
	scanf("%d%d%d",&n,&m,&K);
	int ans=0,O=n*m;
	init(O*2);
	for(int i=0;i<=K;i++)f[i]=((i&1)?-1ll:1ll)*ij[i]*ij[K-i]%mod;
	for(int i=0;i<=O-K;i++)g[i]=1ll*ij[i]*ij[O-K-i]%mod;
	NTT(f,1),NTT(g,1);for(int i=0;i<L;i++)f[i]=1ll*f[i]*g[i]%mod;
	NTT(f,0);
	for(int e=0;e<=O;e++)fp[e]=1ll*jc[e]*jc[O-e]%mod*f[e]%mod;
	/*for(int e=0;e<=O;e++)
		for(int i=0;i<=min(e,K);i++)
		(fp[e]+=((i&1)?-1ll:1ll)*jc[e]*ij[i]*ij[e-i]*jc[O-e]*ij[K-i]*ij[O-e-K+i]%mod)%=mod;*/
	for(int x=0;x<=n;x++)for(int y=0;y<=m;y++){
		int e=x*(m-y)+y*(n-x);
		(ans+=(((x+y)&1)?-1ll:1ll)*C(n,x)*C(m,y)%mod*fp[e]%mod)%=mod;
	}
	return printf("%d",(1ll*ans*i2[n+m]%mod+mod)%mod),0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3 5 7

output:

105

result:

ok single line: '105'

Test #2:

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

input:

4 4 8

output:

144

result:

ok single line: '144'

Test #3:

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

input:

9 7 53

output:

11271960

result:

ok single line: '11271960'

Test #4:

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

input:

10 10 60

output:

711797984

result:

ok single line: '711797984'

Test #5:

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

input:

50 100 100

output:

684521374

result:

ok single line: '684521374'

Test #6:

score: 5
Accepted
time: 10ms
memory: 27424kb

input:

69 69 99

output:

205514286

result:

ok single line: '205514286'

Test #7:

score: 5
Accepted
time: 10ms
memory: 26408kb

input:

500 10 3232

output:

571588252

result:

ok single line: '571588252'

Test #8:

score: 5
Accepted
time: 14ms
memory: 27604kb

input:

70 70 4800

output:

851456413

result:

ok single line: '851456413'

Test #9:

score: 5
Accepted
time: 53ms
memory: 27420kb

input:

100 1000 50000

output:

437541409

result:

ok single line: '437541409'

Test #10:

score: 5
Accepted
time: 48ms
memory: 35452kb

input:

316 316 4238

output:

753478761

result:

ok single line: '753478761'

Test #11:

score: 5
Accepted
time: 50ms
memory: 27760kb

input:

201 479 30001

output:

594408179

result:

ok single line: '594408179'

Test #12:

score: 5
Accepted
time: 194ms
memory: 36648kb

input:

706 706 706

output:

835727049

result:

ok single line: '835727049'

Test #13:

score: 5
Accepted
time: 202ms
memory: 36620kb

input:

2023 233 2023

output:

801992885

result:

ok single line: '801992885'

Test #14:

score: 5
Accepted
time: 93ms
memory: 32180kb

input:

402 402 1000

output:

940937548

result:

ok single line: '940937548'

Test #15:

score: 5
Accepted
time: 91ms
memory: 36388kb

input:

707 333 999

output:

732112489

result:

ok single line: '732112489'

Test #16:

score: 5
Accepted
time: 193ms
memory: 36580kb

input:

600 600 18000

output:

579276872

result:

ok single line: '579276872'

Test #17:

score: 5
Accepted
time: 199ms
memory: 36664kb

input:

389 1047 40001

output:

186903191

result:

ok single line: '186903191'

Test #18:

score: 5
Accepted
time: 204ms
memory: 36432kb

input:

707 707 42837

output:

468460621

result:

ok single line: '468460621'

Test #19:

score: 5
Accepted
time: 190ms
memory: 34460kb

input:

100 5000 32346

output:

460579847

result:

ok single line: '460579847'

Test #20:

score: 5
Accepted
time: 98ms
memory: 31864kb

input:

501 501 251001

output:

1

result:

ok single line: '1'