CF1228E Another Filling the Grid

未分类

---

CF1228E Another Filling the Grid解题报告：

更好的阅读体验

题意

• 给定一个$n\times n$的矩阵，用$[1,k]$中的数填充；
• 要使每行每列最小值都为$1$，问有多少种写法（对$10^9+7$取模）。
• $1\leqslant n\leqslant 250,1\leqslant k\leqslant 10^9$。

分析

容斥又不会做，就是反演这种东西，才能维持的了生活。

首先，因为要使每行每列最小值为$1$，所以每一行都要有$1$。

正难则反，我们不能很快地计算$i$行$j$列每一行列都有$1$，可以尝试设$f_{i,j}$表示矩阵中恰好$i$行$j$列全部没有$1$，$g_{i,j}$表示矩阵中有$i$行$j$列全部没有$1$。

$g_{i,j}$很容易计算，设$now=n^2-(n\cdot i)(n\cdot j)$，则有

$$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}$$