QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#308105#7974. 染色yyyyxh100 ✓163ms43448kbC++232.7kb2024-01-19 15:50:392024-01-19 15:50:39

Judging History

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

  • [2024-01-19 15:50:39]
  • 评测
  • 测评结果:100
  • 用时:163ms
  • 内存:43448kb
  • [2024-01-19 15:50:39]
  • 提交

answer

#include <cstdio>
#include <vector>
#include <algorithm>
#define ALL(vc) (vc).begin(),(vc).end()
using namespace std;
const int N=1000003,P=998244353;
typedef long long ll;
typedef vector<int> vi;
int n,m,k;
int rev[1<<20],cw[1<<20|1];
int ilen,len,bit;
inline void inc(int &x,int v){if((x+=v)>=P) x-=P;}
inline void dec(int &x,int v){if((x-=v)<0) x+=P;}
int qp(int a,int b=P-2){
	int res=1;
	while(b){
		if(b&1) res=(ll)res*a%P;
		a=(ll)a*a%P;b>>=1;
	}
	return res;
}
void init(int _len){
	len=1;bit=-1;
	while(len<_len) len<<=1,++bit;
	int w=qp(3,(P-1)>>(bit+1));
	cw[len]=cw[0]=1;
	for(int i=1;i<len;++i){
		rev[i]=(rev[i>>1]>>1)|((i&1)<<bit);
		cw[i]=(ll)cw[i-1]*w%P;
	}
	ilen=qp(len);
}
struct poly{
	vi f;
	poly(int Len):f(Len){}
	poly(initializer_list<int> Init):f(Init){}
	void NTT(){
		f.resize(len,0);
		for(int i=0;i<len;++i) if(i<rev[i]) swap(f[i],f[rev[i]]);
		for(int i=1,tt=len>>1;i<len;i<<=1,tt>>=1)
			for(int j=0;j<len;j+=(i<<1))
				for(int k=j,t=0;k<(j|i);++k,t+=tt){
					int x=f[k],y=(ll)f[k|i]*cw[t]%P;
					if((f[k]=x+y)>=P) f[k]-=P;
					if((f[k|i]=x-y)<0) f[k|i]+=P;
				}
	}
	void INTT(){
		for(int i=0;i<len;++i) if(i<rev[i]) swap(f[i],f[rev[i]]);
		for(int i=1,tt=len>>1;i<len;i<<=1,tt>>=1)
			for(int j=0;j<len;j+=(i<<1))
				for(int k=j,t=len;k<(j|i);++k,t-=tt){
					int x=f[k],y=(ll)f[k|i]*cw[t]%P;
					if((f[k]=x+y)>=P) f[k]-=P;
					if((f[k|i]=x-y)<0) f[k|i]+=P;
				}
		for(int i=0;i<len;++i) f[i]=(ll)f[i]*ilen%P;
		while(!f.empty()&&!f.back()) f.pop_back();
	}
};
int fac[N],fiv[N];
int C(int n,int k){return (ll)fac[n]*fiv[k]%P*fiv[n-k]%P;}
int a[N],pw[N],res[N];
int main(){
	// freopen("paint.in","r",stdin);
	// freopen("paint.out","w",stdout);
	scanf("%d%d%d",&n,&m,&k);
	int lim=n*m;
	fac[0]=1;
	for(int i=1;i<=lim;++i) fac[i]=(ll)fac[i-1]*i%P;
	fiv[lim]=qp(fac[lim]);
	for(int i=lim;i;--i) fiv[i-1]=(ll)fiv[i]*i%P;
	pw[0]=1;
	for(int i=1;i<=lim;++i) inc(pw[i]=pw[i-1],pw[i-1]);
	for(int i=0;i<=n;++i)
		for(int j=0;j<=m;++j){
			int pos=i*j+(n-i)*(m-j);
			if((i^j)&1){
				a[pos]=(a[pos]-(ll)C(n,i)*C(m,j))%P;
				if(a[pos]<0) a[pos]+=P;
			}
			else a[pos]=(a[pos]+(ll)C(n,i)*C(m,j))%P;
		}
	poly F(lim+1),G(lim+1);
	init(lim<<1|1);
	for(int i=0;i<=lim;++i) F.f[i]=(ll)fac[i]*a[i]%P;
	for(int i=0;i<=lim;++i)
		if(i&1) G.f[i]=P-fiv[i];
		else G.f[i]=fiv[i];
	reverse(ALL(G.f));
	F.NTT();G.NTT();
	poly H(len);
	for(int i=0;i<len;++i) H.f[i]=(ll)F.f[i]*G.f[i]%P;
	H.INTT();
	int Hlen=H.f.size();
	for(int i=lim;i<Hlen;++i) res[lim+lim-i]=(ll)H.f[i]*fiv[i-lim]%P*pw[i-lim]%P;
	int ans=0;
	for(int i=k;i<=lim;++i) ans=(ans+(ll)C(i,k)*res[i])%P;
	ans=(ll)ans*qp(2,P-1-n-m)%P;
	if(ans&&(n&1)) ans=P-ans;
	printf("%d\n",ans);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3 5 7

output:

105

result:

ok single line: '105'

Test #2:

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

input:

4 4 8

output:

144

result:

ok single line: '144'

Test #3:

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

input:

9 7 53

output:

11271960

result:

ok single line: '11271960'

Test #4:

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

input:

10 10 60

output:

711797984

result:

ok single line: '711797984'

Test #5:

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

input:

50 100 100

output:

684521374

result:

ok single line: '684521374'

Test #6:

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

input:

69 69 99

output:

205514286

result:

ok single line: '205514286'

Test #7:

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

input:

500 10 3232

output:

571588252

result:

ok single line: '571588252'

Test #8:

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

input:

70 70 4800

output:

851456413

result:

ok single line: '851456413'

Test #9:

score: 5
Accepted
time: 23ms
memory: 16292kb

input:

100 1000 50000

output:

437541409

result:

ok single line: '437541409'

Test #10:

score: 5
Accepted
time: 24ms
memory: 20128kb

input:

316 316 4238

output:

753478761

result:

ok single line: '753478761'

Test #11:

score: 5
Accepted
time: 24ms
memory: 22084kb

input:

201 479 30001

output:

594408179

result:

ok single line: '594408179'

Test #12:

score: 5
Accepted
time: 154ms
memory: 41124kb

input:

706 706 706

output:

835727049

result:

ok single line: '835727049'

Test #13:

score: 5
Accepted
time: 157ms
memory: 41208kb

input:

2023 233 2023

output:

801992885

result:

ok single line: '801992885'

Test #14:

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

input:

402 402 1000

output:

940937548

result:

ok single line: '940937548'

Test #15:

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

input:

707 333 999

output:

732112489

result:

ok single line: '732112489'

Test #16:

score: 5
Accepted
time: 152ms
memory: 40428kb

input:

600 600 18000

output:

579276872

result:

ok single line: '579276872'

Test #17:

score: 5
Accepted
time: 153ms
memory: 40748kb

input:

389 1047 40001

output:

186903191

result:

ok single line: '186903191'

Test #18:

score: 5
Accepted
time: 159ms
memory: 43448kb

input:

707 707 42837

output:

468460621

result:

ok single line: '468460621'

Test #19:

score: 5
Accepted
time: 163ms
memory: 41112kb

input:

100 5000 32346

output:

460579847

result:

ok single line: '460579847'

Test #20:

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

input:

501 501 251001

output:

1

result:

ok single line: '1'