QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#359475#7974. 染色zjy0001100 ✓54ms23092kbC++174.1kb2024-03-20 18:15:292024-03-20 18:15:30

Judging History

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

  • [2024-03-20 18:15:30]
  • 评测
  • 测评结果:100
  • 用时:54ms
  • 内存:23092kb
  • [2024-03-20 18:15:29]
  • 提交

answer

#include<bits/stdc++.h>
#define LL long long
#define LLL __int128
#define uint unsigned
#define ldb long double
#define uLL unsigned long long
using namespace std;
typedef vector<int> poly;
const int Mod=998244353,G=3,img=86583718,winv=932051910;// winv = 2^64 mod Mod
const int Lim=64,inv2=(Mod+1)/2,inv3=(Mod+1)/3,rinv=Mod-2;
const LL Mod2=(LL)Mod*Mod;
poly w0={1},W0;vector<poly>Tr;
inline int fadd(int x,const int&y){return (x+=y-2*Mod)>=0?x:x+2*Mod;}
inline int fsub(int x,const int&y){return (x-=y)>=0?x:x+2*Mod;}
inline int reduce(LL x){return (x+(LL)((uint)x*rinv)*Mod)>>32;}
inline int qpow(int x,int y,int z=1){
	for(;y;(y>>=1)&&(x=(LL)x*x%Mod))if(y&1)z=(LL)z*x%Mod;return z;
}
inline int BSGS(int x){
	unordered_map<int,int>mp;
	int S=sqrtl(Mod)+1,j=1,q=1;
	for(int i=0;i<S;++i,j=(LL)j*G%Mod)mp[(LL)j*x%Mod]=i;
	for(int i=0;i<=S;++i,q=(LL)q*j%Mod)if(mp.count(q)&&i*S>=mp[q])return i*S-mp[q];
	return -1;
}
inline poly Add(poly P,poly Q){
    if(P.size()<Q.size())swap(P,Q);
    for(int i=Q.size();i--;)(P[i]+=Q[i])>=Mod&&(P[i]-=Mod);
    return P;
}
inline poly Sub(poly P,poly Q){
    if(P.size()<Q.size())P.resize(Q.size());
    for(int i=Q.size();i--;)(P[i]-=Q[i])<0&&(P[i]+=Mod);
    return P;
}
template<int T>inline void dft(poly&P){
	const int m=P.size(),n=m/T,n2=n/2;
    int L=w0.size();
	if(L*2<n)for(w0.resize(n2);L*2<n;L<<=1){
		const int cr=qpow(G,Mod/(L<<2));
		for(int i=0;i<L;++i)w0[i+L]=(LL)cr*w0[i]%Mod;
	}
	if(W0.size()<w0.size()){
		const int pr=W0.size(),ed=w0.size();
		W0.resize(ed);
		for(int i=pr;i<ed;++i)W0[i]=reduce((LL)winv*w0[i]);
	}
	for(int k=n,st1,st2;st1=k*T,st2=st1>>1,k>1;k>>=1)
		for(int i=0,ie=n/k;i<ie;++i)
			for(int p=i*st1,pe=p+st2;p<pe;++p){
				const int q=p+st2,z=reduce((LL)P[q]*W0[i]);
				P[q]=fsub(P[p],z),P[p]=fadd(P[p],z);
			}
    for(int&i:P)i>=Mod&&(i-=Mod);
}
template<int T>inline void idft(poly&P){
	const int m=P.size(),n=m/T,ni=qpow(n,Mod-2),n2=n/2;
	poly rev(n);
	for(int i=1;i<n;++i)rev[i]=(rev[i>>1]>>1)+(i&1)*n2;
	for(int&i:P)i=(LL)i*ni%Mod;
	for(int i=1;i<n;++i)if(i<rev[i])swap_ranges(P.begin()+T*i,P.begin()+T*(i+1),P.begin()+T*rev[i]);
	for(int i=1;i<n2;++i)swap_ranges(P.begin()+T*i,P.begin()+T*(i+1),P.begin()+T*(n-i));
	dft<T>(P);
	for(int i=1;i<n;++i)if(i<rev[i])swap_ranges(P.begin()+T*i,P.begin()+T*(i+1),P.begin()+T*rev[i]);
}
template<int T>inline void mul_mod(poly&P,poly&Q){
	const int m=P.size(),n=m/T;
	dft<T>(P),dft<T>(Q);
	for(int i=0;i<n;++i){
		vector<uLL>ans(T<<1);
		for(int j=0;j<T;++j){
			for(int k=0;k<T;++k)
				ans[j+k]+=(LL)P[i*T+j]*Q[i*T+k];
			if(!((~j)&7))for(int k=j;k<j+T;++k)
				if(ans[k]>=(Mod2<<3))ans[k]-=Mod2<<3;
		}
		const int c=((i&1)?Mod-w0[i>>1]:w0[i>>1]);
		for(int j=T;j--;)P[i*T+j]=(ans[j]+ans[j+T]%Mod*c)%Mod;
	}
	idft<T>(P);
}
template<size_t... m>inline void solve(index_sequence<m...>,int n,poly&P,poly&Q){
	static void (*ptrs[])(poly&,poly&)={&mul_mod<m+1>...};
	ptrs[n-1](P,Q);
}
inline poly Mul(poly P,poly Q){
    if(P.empty()||Q.empty())return poly();
	int pn=P.size(),qn=Q.size(),rn=pn+qn-1,b=1;
	while((Lim<<b)<rn)++b;
	const int T=((rn-1)>>b)+1,m=T<<b;
	P.resize(m),Q.resize(m);
	solve(make_index_sequence<Lim>{},T,P,Q);
	return P.resize(rn),P;
}
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int n,m,k,ans=0;
    cin>>n>>m>>k;
    poly frc(n*m+1),ivf(n*m+1);
    frc[0]=1;
    for(int i=1;i<=n*m;++i)frc[i]=1ll*frc[i-1]*i%Mod;
    ivf[n*m]=qpow(frc[n*m],Mod-2);
    for(int i=n*m;i;--i)ivf[i-1]=1ll*ivf[i]*i%Mod;
    const auto binom=[&](const int&n,const int&m){
        return n<m||m<0?0:1ll*frc[n]*ivf[m]%Mod*ivf[n-m]%Mod;
    };
    poly F(n*m+1),G(n*m+1);
    for(int i=0;i<=n*m;++i){
        if(k>=i)F[i]=1ll*(i&1?Mod-ivf[i]:ivf[i])*ivf[k-i]%Mod;
        if(n*m>=i+k)G[i]=1ll*ivf[i]*ivf[n*m-k-i]%Mod;
    }
    F=Mul(F,G);
    for(int x=0;x<=n;++x)
        for(int y=0;y<=m;++y){
            const int k=x*(m-y)+(n-x)*y;
            assert(k>=0&&k<F.size());
            ans=(ans+(x+y&1?Mod-1ll:1ll)*F[k]%Mod*frc[k]%Mod*frc[n*m-k]%Mod*binom(n,x)%Mod*binom(m,y))%Mod;
        }
    return cout<<qpow(inv2,n+m,ans),0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3 5 7

output:

105

result:

ok single line: '105'

Test #2:

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

input:

4 4 8

output:

144

result:

ok single line: '144'

Test #3:

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

input:

9 7 53

output:

11271960

result:

ok single line: '11271960'

Test #4:

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

input:

10 10 60

output:

711797984

result:

ok single line: '711797984'

Test #5:

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

input:

50 100 100

output:

684521374

result:

ok single line: '684521374'

Test #6:

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

input:

69 69 99

output:

205514286

result:

ok single line: '205514286'

Test #7:

score: 5
Accepted
time: 1ms
memory: 3956kb

input:

500 10 3232

output:

571588252

result:

ok single line: '571588252'

Test #8:

score: 5
Accepted
time: 1ms
memory: 3992kb

input:

70 70 4800

output:

851456413

result:

ok single line: '851456413'

Test #9:

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

input:

100 1000 50000

output:

437541409

result:

ok single line: '437541409'

Test #10:

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

input:

316 316 4238

output:

753478761

result:

ok single line: '753478761'

Test #11:

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

input:

201 479 30001

output:

594408179

result:

ok single line: '594408179'

Test #12:

score: 5
Accepted
time: 46ms
memory: 22904kb

input:

706 706 706

output:

835727049

result:

ok single line: '835727049'

Test #13:

score: 5
Accepted
time: 47ms
memory: 21920kb

input:

2023 233 2023

output:

801992885

result:

ok single line: '801992885'

Test #14:

score: 5
Accepted
time: 17ms
memory: 9816kb

input:

402 402 1000

output:

940937548

result:

ok single line: '940937548'

Test #15:

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

input:

707 333 999

output:

732112489

result:

ok single line: '732112489'

Test #16:

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

input:

600 600 18000

output:

579276872

result:

ok single line: '579276872'

Test #17:

score: 5
Accepted
time: 35ms
memory: 19320kb

input:

389 1047 40001

output:

186903191

result:

ok single line: '186903191'

Test #18:

score: 5
Accepted
time: 54ms
memory: 23092kb

input:

707 707 42837

output:

468460621

result:

ok single line: '468460621'

Test #19:

score: 5
Accepted
time: 47ms
memory: 23092kb

input:

100 5000 32346

output:

460579847

result:

ok single line: '460579847'

Test #20:

score: 5
Accepted
time: 22ms
memory: 13344kb

input:

501 501 251001

output:

1

result:

ok single line: '1'