题解 | #牛牛的棋盘#

题意整理

给定 $n*m$ 的矩阵以及 $k$ 个点。
现在要将这 $k$ 个点放在矩阵里，并且保证第一行，第一列，最后一行，最后一列都有点。
求总共有多少种方案。

方法一（动态规划）

1.解题思路

初始化一个组合数组 $f$ ， $f[i][j]$ 表示在i个格子里取j个点的组合数，即 $C_{i}^{j}$ 。
根据组合递归公式 $C_{i}^{j}=C_{i-1}^{j-1}+C_{i-1}^{j}$ ，可得： $f[i][j]=f[i-1][j-1]+f[i-1][j]$ 。
计算出所有的组合数之后，首先取 $C_{n*m}^{k}$ 对应的所有组合数，然后排除第1列或最后一列没点的情况 $2*C_{n*(m-1)}^{k}$ 以及第1行或最后一行没点的情况 $2*C_{(n-1)*m}^{k}$ ，加上多排除的1行1列没点的情况 $4*C_{(n-1)*(m-1)}^{k}$ ，加上多排除的第1列和最后一列没点的情况 $C_{n*(m-2)}^{k}$ ，加上多排除的第1行和最后一行没点的情况 $C_{(n-2)*m}^{k}$ ，继续排除2行1列没点的情况 $2*C_{(n-2)*(m-1)}^{k}$ ，继续排除1行2列没点的情况 $2*C_{(n-1)*(m-2)}^{k}$ ，加上多排除的2行2列没点的情况 $C_{(n-2)*(m-2)}^{k}$ 。

动图展示：
图片说明

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 
     * @param n int整型 
     * @param m int整型 
     * @param k int整型 
     * @return int整型
     */
    //取余常数
    int mod=1000000007;
    //组合数组
    int[][] f;
    int n,m,k;

    public int solve (int n, int m, int k) {
        this.n=n;
        this.m=m;
        this.k=k;
        this.f=new int[n*m+1][k+1];
        //初始化组合数组
        initMap();
        //取k个点的所有组合数
        long res=f[n*m][k]%mod;
        //排除第1列或最后一列没点的情况
        res=(res-2*f[n*(m-1)][k]%mod+mod)%mod;
        //排除第1行或最后一行没点的情况
        res=(res-2*f[(n-1)*m][k]%mod+mod)%mod;
        //加上多排除的1行1列没点的情况
        res=(res+4*(long)f[(n-1)*(m-1)][k]%mod)%mod;
        //加上多排除的第1列和最后一列没点的情况
        res=(res+f[n*(m-2)][k])%mod;
        //加上多排除的第1行和最后一行没点的情况
        res=(res+f[(n-2)*m][k])%mod;
        //排除2行1列没点的情况
        res=(res-2*f[(n-2)*(m-1)][k]%mod+mod)%mod;
        //排除1行2列没点的情况
        res=(res-2*f[(n-1)*(m-2)][k]%mod+mod)%mod;
        //加上多排除的2行2列没点的情况
        res=(res+f[(n-2)*(m-2)][k]%mod)%mod;

        return (int)res;
    }

    //根据递推公式C(n,m)=C(n-1,m-1)+C(n-1,m)，计算每一个组合数
    private void initMap(){
        //从i个格子中选一个点的情况，相当于C(i,1)
        for(int i=1;i<=n*m;i++){
            f[i][1]=i;
        }

        //从i个格子中选j个点的情况
        for(int i=1;i<=n*m;i++){
            for(int j=2;j<=k;j++){
                f[i][j]=(f[i-1][j-1]+f[i-1][j])%mod;
            }
        }
    }
}

3.复杂度分析

时间复杂度：初始化组合数组时，循环次数为 $n*m*k$ ，所以时间复杂度是 $O(n*m*k)$ 。
空间复杂度：需要额外大小为 $(n*m+1)*(k+1)$ 的存储空间，所以空间复杂度是 $O(n*m*k)$ 。

方法二（数学）

1.解题思路

思路和方法一的大致相同，仍然是先计算所有的组合数，然后排除掉不可能的情况，由于排除的情况可能会重叠，需要把多排除的情况再加上。
计算组合数时，为了防止溢出，使用大数运算，先求大数阶乘，然后根据阶乘计算对应的组合。

2.代码实现

import java.util.*;
import java.math.BigInteger;

public class Solution {
    /**
     * 
     * @param n int整型 
     * @param m int整型 
     * @param k int整型 
     * @return int整型
     */
    //定义要用到的一些常量
    final BigInteger ONE=new BigInteger("1");
    final BigInteger TWO=new BigInteger("2");
    final BigInteger FOUR=new BigInteger("4");
    final BigInteger MOD=new BigInteger("1000000007");

    public int solve (int n, int m, int k) {
        //初始化结果变量
        BigInteger res=C(n*m,k);
        //排除不满足约束的情况，并加上多排除的情况
        res=res.subtract(C(n*(m-1),k).multiply(TWO));
        res=res.subtract(C((n-1)*m,k).multiply(TWO));
        res=res.add(C((n-1)*(m-1),k).multiply(FOUR));
        res=res.add(C(n*(m-2),k));
        res=res.add(C((n-2)*m,k));
        res=res.subtract(C((n-2)*(m-1),k).multiply(TWO));
        res=res.subtract(C((n-1)*(m-2),k).multiply(TWO));
        res=res.add(C((n-2)*(m-2),k));
        //取余
        res=res.mod(MOD);
        return res.intValue();
    }

    //计算大数组合
    private BigInteger C(int n,int m){
        return factorial(n).divide(factorial(m).multiply(factorial(n-m)));
    }

    //计算大数阶乘
    private BigInteger factorial(int n){
        BigInteger res=ONE;
        for(int i=2;i<=n;i++){
            BigInteger I=new BigInteger(String.valueOf(i));
            res=res.multiply(I);
        }
        return res;
    }
}

3.复杂度分析

时间复杂度：计算阶乘的时间复杂度为 $O(n)$ ，计算对应的组合需要计算常数次阶乘，所以计算组合数的时间复杂度为 $O(n)$ ，总共需要计算常数次组合数，所以最终的时间复杂度是 $O(n)$ 。
空间复杂度：需要额外常数级别的存储空间，所以空间复杂度是 $O(1)$ 。