题目

Luogu

CF

给定一个\(n\cdot n\)的矩阵，用\(1\)到\(k\)填充，要求每行每列至少有\(1\)个\(1\)​，求方案数。

Sol

感觉和一道三色填充的题有一些共同之处。CF997C

但是这道题可以\(O(n^3)\)（应该吧）。

所以仔细转化一下题意就可以有容斥的思路。

枚举\(i,j\)，表示钦定\(i\)行\(j\)列不合法，剩下的随便放。

如何保证不合法呢？强制只能选取\(2\)到\(k\)的整数就行了。

\[ans=\sum\limits_{i=0}^n\sum\limits_{j=0}^n(-1)^{i+j}\binom{n}{i}\binom{n}{j}k^{(n-i)(n-j)}(k-1)^{n\cdot n-(n-i)(n-j)} \]

\(k^{(n-i)(n-j)}\)的意思是除去强制不合法的\(i\)​行\(j\)列以外其余的随便放。

复杂度\(O(n^2log\ n)\)。

可以预处理快速幂省掉一个\(log\)​，但没必要。

Code

#include<bits/stdc++.h>
#define N (255)
#define ll long long
using namespace std;
const ll P=1000000007;
ll n,K,ans,fc[N],inv[N];
inline ll read(){
	ll w=0;
	char ch=getchar();
	while(ch>'9'||ch<'0') ch=getchar();
	while(ch>='0'&&ch<='9'){
		w=(w<<3)+(w<<1)+(ch^48);
		ch=getchar();
	}
	return w;
}
inline ll ksm(ll a,ll b){
	ll res=1;
	while(b){
		if(b&1) res=res*a%P;
		a=a*a%P;
		b>>=1;
	}
	return res;
}
int main(){
	n=read(),K=read();
	fc[0]=inv[0]=1;
	for(ll i=1;i<=n;i++) fc[i]=fc[i-1]*i%P;
	inv[n]=ksm(fc[n],P-2);
	for(ll i=n-1;i>=1;i--) inv[i]=inv[i+1]*(i+1)%P;
	for(ll i=0;i<=n;i++){
		for(ll j=0;j<=n;j++){
			ll res1=fc[n]*inv[i]%P*inv[n-i]%P*fc[n]%P*inv[j]%P*inv[n-j]%P;
			ll res2=ksm(K,(n-i)*(n-j))*ksm(K-1,n*i+n*j-i*j)%P;
			ll res=res1*res2%P;
			if((i+j)&1) ans=(ans-res+P)%P;
			else ans=(ans+res)%P;
		}
	}
	printf("%lld\n",ans);
	return 0;
}

完结撒花❀