题解 CF1228E 【Another Filling the Grid】
whiteqwq
·
·
题解
CF1228E Another Filling the Grid解题报告：
更好的阅读体验
题意
- 给定一个n\times n的矩阵，用[1,k]中的数填充；
- 要使每行每列最小值都为1，问有多少种写法（对10^9+7取模）。
-
分析
容斥又不会做，就是反演这种东西，才能维持的了生活。
首先，因为要使每行每列最小值为1，所以每一行都要有1。
正难则反，我们不能很快地计算i行j列每一行列都有1，可以尝试设f_{i,j}表示矩阵中恰好i行j列全部没有1，g_{i,j}表示矩阵中有i行j列全部没有1。
$$g_{i,j}={n\choose i}{m\choose j}(k-1)^{now}k^{n^2-now}$$
根据$g_{i,j}$的定义，很显然有：
$$g_{i,j}=\sum_{x=i}^n\sum_{y=j}^n{x\choose i}{y\choose j}f_{x,y}$$
对于上面的式子，我们可以使用二项式反演来得到另一个式子：
$$f_{i,j}=\sum_{x=i}^n\sum_{y=i}^n{x\choose i}{y\choose j}(-1)^{(x-i)+(y-j)}g_{x,y}$$
最后，我们的答案就是$f_{0,0}$了。
具体地，我们可以首先$O(n+\log mod)$预处理逆元，然后$O(n^2)$求$g$数组，然后通过$i=0,j=0$带入上式得到$\sum_{x=0}^n\sum_{y=0}^n{x\choose 0}{y\choose 0}(-1)^{(x-0)+(y-0)}g_{x,y}=\sum_{x=0}^n\sum_{y=0}^n(-1)^{x+y}g_{x,y}$，直接$O(n^2)$计算就好了。
复杂度：$O(n^2)$。
## 代码
```
#include<stdio.h>
#define int long long
const int maxn=2005,mod=1000000007;
int n,k,ans;
int fac[maxn],nfac[maxn],g[maxn][maxn],f[maxn][maxn],amul[maxn*maxn],bmul[maxn*maxn];
inline int c(int n,int m){
return fac[n]*nfac[n-m]%mod*nfac[m]%mod;
}
int ksm(int a,int b){
int res=1;
while(b){
if(b&1)
res=res*a%mod;
a=a*a%mod,b>>=1;
}
return res;
}
signed main(){
fac[0]=1;
for(int i=1;i<maxn;i++)
fac[i]=fac[i-1]*i%mod;
nfac[maxn-1]=ksm(fac[maxn-1],mod-2);
for(int i=maxn-1;i>=1;i--)
nfac[i-1]=nfac[i]*i%mod;
scanf("%lld%lld",&n,&k);
amul[0]=bmul[0]=1;
for(int i=1;i<=n*n;i++)
amul[i]=amul[i-1]*(k-1)%mod,bmul[i]=bmul[i-1]*k%mod;
for(int i=0;i<=n;i++)
for(int j=0;j<=n;j++){
g[i][j]=c(n,i)*c(n,j)%mod*amul[n*n-(n-i)*(n-j)]%mod*bmul[(n-i)*(n-j)]%mod;
}
for(int i=0;i<=n;i++)
for(int j=0;j<=n;j++){
if((i+j)%2==0)
ans=(ans+g[i][j])%mod;
else ans=(ans-g[i][j]+mod)%mod;
}
printf("%lld\n",(ans+mod)%mod);
return 0;
}
```
## 二项式反演证明
二维二项式反演证明（这里式子不太一样，但原理差不多，懒得改了）：
$$f_{n,m}=\sum_{i=0}^n\sum_{j=0}^m{n\choose i}{m\choose j}g_{i,j}\Rightarrow g_{n,m}=\sum_{i=0}^n\sum_{j=0}^m{n\choose i}{m\choose j}(-1)^{(n-i)+(m-j)}f_{i,j}$$
设$F_i=f_{i,m}$，$G_i=\sum_{j=0}^m{m\choose j}g_{i,j}$，那么由上式得：
$$F_n=\sum_{i=0}^n{n\choose i}G_i$$
然后由二项式反演得：
$$G_n=\sum_{i=0}^n{n\choose i}(-1)^{n-i}F_i$$
展开有：
$$\sum_{j=0}^m{m\choose j}g_{n,j}=\sum_{i=0}^n{n\choose i}(-1)^{n-i}f_{i,m}$$
再设$F_i'=\sum_{j=0}^n{n\choose j}(-1)^{n-j}f_{j,i}$，$G_i'=g_{n,i}$，那么代入上式有：
$$F_m'=\sum_{j=0}^m{m\choose j}G_j'$$
然后继续二项式反演：
$$G_m'=\sum_{j=0}^m{m\choose j}(-1)^{m-j}F_j'$$
展开有：
$$g_{n,m}=\sum_{j=0}^m{m\choose j}(-1)^{m-j}\sum_{i=0}^n{n\choose i}(-1)^{n-i}f_{i,j}$$
然后整理一下就有上面的式子了：
$$g_{n,m}=\sum_{i=0}^n\sum_{j=0}^m{n\choose i}{m\choose j}(-1)^{(n-i)+(m-j)}f_{i,j}$$