QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#286653#7974. 染色zhouhuanyi100 ✓129ms128072kbC++202.7kb2023-12-18 10:11:152023-12-18 10:11:15

Judging History

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

  • [2023-12-18 10:11:15]
  • 评测
  • 测评结果:100
  • 用时:129ms
  • 内存:128072kb
  • [2023-12-18 10:11:15]
  • 提交

answer

#include<iostream>
#include<cstdio>
#define N 500000
#define M 1048576
#define K 21
#define g 3
#define mod 998244353
using namespace std;
int read()
{
	char c=0;
	int sum=0;
	while (c<'0'||c>'9') c=getchar();
	while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
	return sum;
}
int fast_pow(int a,int b)
{
	int res=1,mul=a;
	while (b)
	{
		if (b&1) res=1ll*res*mul%mod;
		mul=1ll*mul*mul%mod,b>>=1;
	}
	return res;
}
int MD(int x)
{
	return x>=mod?x-mod:x;
}
int MD2(int x)
{
	return x<0?x+mod:x;
}
void Adder(int &x,int d)
{
	x+=d;
	if (x>=mod) x-=mod;
	return;
}
void Adder2(int &x,int d)
{
	x+=d;
	if (x<0) x+=mod;
	return;
}
int n,m,k,length,rev[M+1],num[M+1],wn[K+1][M+1],wn2[K+1][M+1],limit=1,ans,F[N+1],G[N+1],fac[N+1],invfac[N+1],A[M+1],B[M+1];
int C(int x,int y)
{
	if (x<y) return 0;
	return 1ll*fac[x]*invfac[y]%mod*invfac[x-y]%mod;
}
void NTT(int limit,int *s,int type)
{
	int s1,s2;
	for (int i=1;i<limit;++i) rev[i]=(rev[i>>1]>>1)|((i&1)?limit>>1:0);
	for (int i=1;i<limit;++i)
		if (rev[i]>i)
			swap(s[i],s[rev[i]]);
	if (type==1)
	{
		for (int i=2;i<=limit;i<<=1)
			for (int j=0;j+i-1<limit;j+=i)
				for (int k=j;k<j+(i>>1);++k)
					s1=s[k],s2=1ll*s[k+(i>>1)]*wn[num[i]][k-j]%mod,s[k]=MD(s1+s2),s[k+(i>>1)]=MD2(s1-s2);
	}
	else
	{
		for (int i=2;i<=limit;i<<=1)
			for (int j=0;j+i-1<limit;j+=i)
				for (int k=j;k<j+(i>>1);++k)
					s1=s[k],s2=1ll*s[k+(i>>1)]*wn2[num[i]][k-j]%mod,s[k]=MD(s1+s2),s[k+(i>>1)]=MD2(s1-s2);
		s1=fast_pow(limit,mod-2);
		for (int i=0;i<=limit;++i) s[i]=1ll*s[i]*s1%mod;
	}
	return;
}
int main()
{
	fac[0]=1;
	for (int i=1;i<=N;++i) fac[i]=1ll*fac[i-1]*i%mod;
	invfac[N]=fast_pow(fac[N],mod-2);
	for (int i=N-1;i>=0;--i) invfac[i]=1ll*invfac[i+1]*(i+1)%mod;
	for (int i=2,w;i<=M;i<<=1)
	{
		num[i]=++length,w=fast_pow(g,(mod-1)/i);
		for (int j=0,res=1;j<(i>>1);++j,res=1ll*res*w%mod) wn[num[i]][j]=res;
		w=fast_pow(g,(mod-1)/i*(i-1));
		for (int j=0,res=1;j<(i>>1);++j,res=1ll*res*w%mod) wn2[num[i]][j]=res;
	}
	n=read(),m=read(),k=read();
	for (int i=0;i<=n;++i)
		for (int j=0;j<=m;++j)
		{
			if (!((i+j)&1)) Adder(F[i*j+(n-i)*(m-j)],1ll*C(n,i)*C(m,j)%mod);
			else Adder2(F[i*j+(n-i)*(m-j)],-1ll*C(n,i)*C(m,j)%mod);
		}
	while (limit<=((n*m)<<1)) limit<<=1;
	for (int i=0;i<=n*m;++i) A[i]=1ll*F[i]*fac[n*m-i]%mod,B[i]=invfac[i];
	NTT(limit,A,1),NTT(limit,B,1);
	for (int i=0;i<=limit;++i) A[i]=1ll*A[i]*B[i]%mod;
	NTT(limit,A,-1);
	for (int i=0;i<=n*m;++i) G[i]=1ll*A[i]*invfac[n*m-i]%mod;
	for (int i=0,rst=1;i<=k;++i,rst=1ll*rst*(mod-2)%mod) Adder(ans,1ll*G[n*m-i]*rst%mod*C(n*m-i,k-i)%mod);
	printf("%lld\n",1ll*ans*fast_pow(2,mod-1-(n+m))%mod);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3 5 7

output:

105

result:

ok single line: '105'

Test #2:

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

input:

4 4 8

output:

144

result:

ok single line: '144'

Test #3:

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

input:

9 7 53

output:

11271960

result:

ok single line: '11271960'

Test #4:

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

input:

10 10 60

output:

711797984

result:

ok single line: '711797984'

Test #5:

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

input:

50 100 100

output:

684521374

result:

ok single line: '684521374'

Test #6:

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

input:

69 69 99

output:

205514286

result:

ok single line: '205514286'

Test #7:

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

input:

500 10 3232

output:

571588252

result:

ok single line: '571588252'

Test #8:

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

input:

70 70 4800

output:

851456413

result:

ok single line: '851456413'

Test #9:

score: 5
Accepted
time: 40ms
memory: 128072kb

input:

100 1000 50000

output:

437541409

result:

ok single line: '437541409'

Test #10:

score: 5
Accepted
time: 30ms
memory: 119080kb

input:

316 316 4238

output:

753478761

result:

ok single line: '753478761'

Test #11:

score: 5
Accepted
time: 31ms
memory: 105612kb

input:

201 479 30001

output:

594408179

result:

ok single line: '594408179'

Test #12:

score: 5
Accepted
time: 124ms
memory: 119320kb

input:

706 706 706

output:

835727049

result:

ok single line: '835727049'

Test #13:

score: 5
Accepted
time: 129ms
memory: 123660kb

input:

2023 233 2023

output:

801992885

result:

ok single line: '801992885'

Test #14:

score: 5
Accepted
time: 66ms
memory: 115536kb

input:

402 402 1000

output:

940937548

result:

ok single line: '940937548'

Test #15:

score: 5
Accepted
time: 67ms
memory: 116040kb

input:

707 333 999

output:

732112489

result:

ok single line: '732112489'

Test #16:

score: 5
Accepted
time: 129ms
memory: 118188kb

input:

600 600 18000

output:

579276872

result:

ok single line: '579276872'

Test #17:

score: 5
Accepted
time: 128ms
memory: 113728kb

input:

389 1047 40001

output:

186903191

result:

ok single line: '186903191'

Test #18:

score: 5
Accepted
time: 125ms
memory: 114504kb

input:

707 707 42837

output:

468460621

result:

ok single line: '468460621'

Test #19:

score: 5
Accepted
time: 129ms
memory: 114584kb

input:

100 5000 32346

output:

460579847

result:

ok single line: '460579847'

Test #20:

score: 5
Accepted
time: 60ms
memory: 116324kb

input:

501 501 251001

output:

1

result:

ok single line: '1'