QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#305986#7974. 染色JohnAlfnov100 ✓119ms29532kbC++141.8kb2024-01-16 07:52:362024-01-16 07:52:36

Judging History

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

  • [2024-01-16 07:52:36]
  • 评测
  • 测评结果:100
  • 用时:119ms
  • 内存:29532kb
  • [2024-01-16 07:52:36]
  • 提交

answer

#include<bits/stdc++.h>
#define mod 998244353
#define en 499122177
using namespace std;
int di[500005],id[500005];
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 C(int n,int m){
	if(n<0||m<0||n<m)return 0;
	return 1ll*di[n]*id[m]%mod*id[n-m]%mod;
}
int a[1<<21],ap[1<<21];
int b[1<<21],bp[1<<21];
int rev[1<<21];
void ntt(int l,int *c,int *d,int gs){
	for(int i=0;i<(1<<l);++i)d[rev[i]]=c[i];
	for(int i=1;i<(1<<l);i<<=1){
		int o1=powdv(3,(mod-1)/i/2);
		if(gs==-1)o1=powdv(o1);
		for(int j=0;j<(1<<l);j+=i+i){
			int o=1;
			for(int k=j;k<j+i;++k){
				int A=d[k],B=d[k+i];
				d[k]=(A+1ll*o*B)%mod,d[k+i]=(A-1ll*o*B)%mod;
				o=1ll*o*o1%mod;
			}
		}
	}
	if(gs==-1){
		int cj=1;
		for(int i=1;i<=l;++i)cj=1ll*cj*en%mod;
		for(int i=0;i<(1<<l);++i)d[i]=1ll*d[i]*cj%mod;
	}
}
int sc[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;
	for(int i=0;i<=k;++i)a[i]=1ll*(i%2==0?1:-1)*id[i]*id[k-i]%mod;
	for(int i=0;i<=N-k;++i)b[i]=1ll*id[i]*id[N-k-i]%mod;
	int cd=N+1;
	while(cd&(cd-1))++cd;
	int l=__builtin_ctz(cd);
	for(int i=0;i<(1<<l);++i){
		for(int j=0;j<l;++j)if(i&(1<<j))rev[i]^=1<<(l-j-1);
	}
	ntt(l,a,ap,1);
	ntt(l,b,bp,1);
	for(int i=0;i<(1<<l);++i)ap[i]=1ll*ap[i]*bp[i]%mod;
	ntt(l,ap,a,-1);
	for(int i=0;i<=N;++i)sc[i]=1ll*a[i]*di[i]%mod*di[N-i]%mod;
	int ans=0;
	for(int s=0;s<=n;++s)for(int t=0;t<=m;++t){
		int xs=1ll*((s+t)%2==0?1:-1)*C(n,s)*C(m,t)%mod;
		int gs=s*m+t*n-2*s*t;
		ans=(ans+1ll*xs*sc[gs])%mod;
	}
	for(int i=1;i<=n+m;++i)ans=1ll*ans*en%mod;
	ans=(ans+mod)%mod;
	printf("%d\n",ans);
	return 0;
}

详细

Test #1:

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

input:

3 5 7

output:

105

result:

ok single line: '105'

Test #2:

score: 5
Accepted
time: 3ms
memory: 18244kb

input:

4 4 8

output:

144

result:

ok single line: '144'

Test #3:

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

input:

9 7 53

output:

11271960

result:

ok single line: '11271960'

Test #4:

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

input:

10 10 60

output:

711797984

result:

ok single line: '711797984'

Test #5:

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

input:

50 100 100

output:

684521374

result:

ok single line: '684521374'

Test #6:

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

input:

69 69 99

output:

205514286

result:

ok single line: '205514286'

Test #7:

score: 5
Accepted
time: 3ms
memory: 18128kb

input:

500 10 3232

output:

571588252

result:

ok single line: '571588252'

Test #8:

score: 5
Accepted
time: 3ms
memory: 18248kb

input:

70 70 4800

output:

851456413

result:

ok single line: '851456413'

Test #9:

score: 5
Accepted
time: 29ms
memory: 28728kb

input:

100 1000 50000

output:

437541409

result:

ok single line: '437541409'

Test #10:

score: 5
Accepted
time: 29ms
memory: 26860kb

input:

316 316 4238

output:

753478761

result:

ok single line: '753478761'

Test #11:

score: 5
Accepted
time: 28ms
memory: 18616kb

input:

201 479 30001

output:

594408179

result:

ok single line: '594408179'

Test #12:

score: 5
Accepted
time: 115ms
memory: 29532kb

input:

706 706 706

output:

835727049

result:

ok single line: '835727049'

Test #13:

score: 5
Accepted
time: 118ms
memory: 29148kb

input:

2023 233 2023

output:

801992885

result:

ok single line: '801992885'

Test #14:

score: 5
Accepted
time: 52ms
memory: 18812kb

input:

402 402 1000

output:

940937548

result:

ok single line: '940937548'

Test #15:

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

input:

707 333 999

output:

732112489

result:

ok single line: '732112489'

Test #16:

score: 5
Accepted
time: 117ms
memory: 25268kb

input:

600 600 18000

output:

579276872

result:

ok single line: '579276872'

Test #17:

score: 5
Accepted
time: 118ms
memory: 25532kb

input:

389 1047 40001

output:

186903191

result:

ok single line: '186903191'

Test #18:

score: 5
Accepted
time: 115ms
memory: 28800kb

input:

707 707 42837

output:

468460621

result:

ok single line: '468460621'

Test #19:

score: 5
Accepted
time: 119ms
memory: 29308kb

input:

100 5000 32346

output:

460579847

result:

ok single line: '460579847'

Test #20:

score: 5
Accepted
time: 57ms
memory: 19144kb

input:

501 501 251001

output:

1

result:

ok single line: '1'