QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#419671#7974. 染色kkkgjyismine4100 ✓453ms29456kbC++142.0kb2024-05-24 08:55:122024-05-24 08:55:13

Judging History

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

  • [2024-05-24 08:55:13]
  • 评测
  • 测评结果:100
  • 用时:453ms
  • 内存:29456kb
  • [2024-05-24 08:55:12]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353,mx=5e5;
int fac[500005],ifac[500005];
int mul(int a,int b){return 1ll*a*b%mod;}
void add(int &x,const int y){if((x+=y)>=mod)x-=mod;}
void sub(int &x,const int y){if((x+=(mod-y))>=mod)x-=mod;}
int C(int n,int m){if(n<m)return 0;return mul(fac[n],mul(ifac[m],ifac[n-m]));}
int n,m,k,Wn[1<<21|1],f[1<<21|1],g[1<<21|1],limit,L,r[1<<21|1];
int qpow(int a,int b){
	int c=1;
	while(b){if(b&1)c=mul(c,a);a=mul(a,a),b>>=1;}
	return c;
}
void ntt(int *a,int o){
	for(int i=0;i<limit;++i)if(i<r[i])swap(a[i],a[r[i]]);int now=3;if(o<0)now=qpow(3,mod-2);
	for(int m=1;m<limit;m<<=1){
        int Gi=qpow(now,mod/(m<<1));
        Wn[0]=1;for(int j=1;j<=m;++j)Wn[j]=mul(Wn[j-1],Gi);
        for(int i=0;i<limit;i+=(m<<1))
         for(int j=0;j<m;++j){
         	int x=a[i+j],y=mul(a[i+j+m],Wn[j]);
         	a[i+j]=x+y,a[i+j+m]=x+mod-y;
         	if(a[i+j]>=mod)a[i+j]-=mod;
         	if(a[i+j+m]>=mod)a[i+j+m]-=mod;
		 }
	}
	if(o<0){
		int inv=qpow(limit,mod-2);
		for(int i=0;i<limit;++i)a[i]=mul(a[i],inv);
	}
}
int main(){
	cin>>n>>m>>k;
	fac[0]=ifac[0]=ifac[1]=1;
	for(int i=1;i<=mx;++i)fac[i]=mul(fac[i-1],i);
	for(int i=2;i<=mx;++i)ifac[i]=mul(ifac[mod%i],mod-mod/i);
	for(int i=1;i<=mx;++i)ifac[i]=mul(ifac[i],ifac[i-1]);
    limit=1,L=0;while(limit<=2*n*m)limit<<=1,++L;
    for(int i=0;i<limit;++i)r[i]=((r[i>>1]>>1)|((i&1)<<L-1));
    for(int i=0;i<=k;++i){
    	f[i]=mul(ifac[i],ifac[k-i]);
    	if(i&1)f[i]=(mod-f[i])%mod;
	}
	for(int d=0;d<=n*m;++d)if(n*m-k-d>=0)g[d]=mul(ifac[n*m-k-d],ifac[d]);
	ntt(f,1),ntt(g,1);
	for(int i=0;i<limit;++i)f[i]=mul(f[i],g[i]);ntt(f,-1);
	for(int i=0;i<=n*m;++i)f[i]=mul(f[i],mul(fac[i],fac[n*m-i]));
	int ans=0;
	for(int i=0;i<=n;++i)
	  for(int j=0;j<=m;++j){
	  	int ct=(n-i)*j+i*(m-j);
	  	if((i+j)&1)sub(ans,mul(f[ct],mul(C(n,i),C(m,j))));
	  	else add(ans,mul(f[ct],mul(C(n,i),C(m,j))));
	  }
	int inv2=(mod+1)/2;
	for(int i=1;i<=n+m;++i)ans=mul(ans,inv2);
	cout<<ans;
	return 0;
}

详细

Test #1:

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

input:

3 5 7

output:

105

result:

ok single line: '105'

Test #2:

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

input:

4 4 8

output:

144

result:

ok single line: '144'

Test #3:

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

input:

9 7 53

output:

11271960

result:

ok single line: '11271960'

Test #4:

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

input:

10 10 60

output:

711797984

result:

ok single line: '711797984'

Test #5:

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

input:

50 100 100

output:

684521374

result:

ok single line: '684521374'

Test #6:

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

input:

69 69 99

output:

205514286

result:

ok single line: '205514286'

Test #7:

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

input:

500 10 3232

output:

571588252

result:

ok single line: '571588252'

Test #8:

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

input:

70 70 4800

output:

851456413

result:

ok single line: '851456413'

Test #9:

score: 5
Accepted
time: 81ms
memory: 21460kb

input:

100 1000 50000

output:

437541409

result:

ok single line: '437541409'

Test #10:

score: 5
Accepted
time: 88ms
memory: 22492kb

input:

316 316 4238

output:

753478761

result:

ok single line: '753478761'

Test #11:

score: 5
Accepted
time: 90ms
memory: 23944kb

input:

201 479 30001

output:

594408179

result:

ok single line: '594408179'

Test #12:

score: 5
Accepted
time: 370ms
memory: 26664kb

input:

706 706 706

output:

835727049

result:

ok single line: '835727049'

Test #13:

score: 5
Accepted
time: 355ms
memory: 28624kb

input:

2023 233 2023

output:

801992885

result:

ok single line: '801992885'

Test #14:

score: 5
Accepted
time: 181ms
memory: 18200kb

input:

402 402 1000

output:

940937548

result:

ok single line: '940937548'

Test #15:

score: 5
Accepted
time: 188ms
memory: 18672kb

input:

707 333 999

output:

732112489

result:

ok single line: '732112489'

Test #16:

score: 5
Accepted
time: 445ms
memory: 29456kb

input:

600 600 18000

output:

579276872

result:

ok single line: '579276872'

Test #17:

score: 5
Accepted
time: 453ms
memory: 27616kb

input:

389 1047 40001

output:

186903191

result:

ok single line: '186903191'

Test #18:

score: 5
Accepted
time: 387ms
memory: 29136kb

input:

707 707 42837

output:

468460621

result:

ok single line: '468460621'

Test #19:

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

input:

100 5000 32346

output:

460579847

result:

ok single line: '460579847'

Test #20:

score: 5
Accepted
time: 155ms
memory: 19252kb

input:

501 501 251001

output:

1

result:

ok single line: '1'