题解 | #牛牛的棋盘#

牛牛的棋盘

http://www.nowcoder.com/practice/18894b43f1794d4b959384b8db70004a

牛牛的棋盘

描述
n*m的矩阵，k个点，将k个点全部放在n*m的矩阵里，求满足以下约束的方案数：
矩阵第一行，第一列，最后一行，最后一列都有点。
输出方案数对1e9+7的模数
示例
输入：2,3,1
返回值：0
说明：就1个点，所以无法满足条件。
示例2
输入：2,2,2
返回值：2
说明：我们可以把1个点放在左上角，第一个点放在右下角；也可以把一个点放在右上角，一个点放在左下角。故而有2种放法。
这应该是在n*m-2个位置中选取k-2个位置,数学中组合算法，!(n*m-2)/(!(k-2)*!(n*m-k))需要化简下公式感叹号的意思是阶乘(从1乘到当前数)

方法一

思路分析

最近在上组合数学这门课程，刚好可以利用所学的容斥原理解决这道题目。容斥原理的基本思想是：先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复，这种计数的方法称为容斥原理。因此计算步骤如下：

不考虑约束的情况下，总的方案数设置为$S$，总的方案数为，在$n*m$个位置上选择k个数即可，即 $C_{k}^{n*m}$
设 $p_{i},i=1,2,3,4$ 分别表示矩阵第一行没有点，矩阵第一列没有点，矩阵最后一行没有点，矩阵最后一列没有点的性质
利用 $A_{i}$ 表示满足 $p_{i}$ 性质的方案数，例如 $A_{1}$ 表示矩阵第一行没有点的方案数， $A_{2}$ 表示矩阵第一列没有点的方案数， $A_{3}$ 表示矩阵最后一行没有点的方案数， $A_{4}$ 表示矩阵最后一列没有点的方案数
那么 $|\bar{A_{1}}\cap \bar{A_{2}}\cap \bar{A_{3}}\cap \bar{A_{4}}|$ 表示矩阵第一行，第一列，最后一行，最后一列都有点的方案数，并且有如下的计算公式： $|\bar{A_{1}}\cap \bar{A_{2}}\cap \bar{A_{3}}\cap \bar{A_{4}}|=|S|- \sum_{i=1}^{4}{|A_{i}|}+\sum_{i\ne j}{|A_{i}\cap A_{j}|}-\sum_{i \ne j\ne k}{|A_{i}\cap A_{j}\cap A_{k}|}+\sum{|A_{1}\cap A_{2}\cap A_{3} \cap A_{4}|}$
利用上面的公式可以得到满足约束条件的方案数

图解计算过程

核心代码

class Solution {
public:
    /**
     *
     * @param n int整型
     * @param m int整型
     * @param k int整型
     * @return int整型
     */
	const int mod=1e9+7;
    long long f[1000];
    int solve(int n, int m, int k) {
        f[0]=1;
        for(int i=1;i<=1000;i++)
           f[i]=f[i-1]*i%mod;
        vector<long long> s(5,0);//存储组合数
        s[0]=C(n*m,k)%mod;//总的方案数
        s[1]=2*(C((n-1)*m,k)+C(n*(m-1),k))%mod;//满足其中一种性质的方案数
        s[2]=(4*C((n-1)*(m-1),k)+C((n-2)*m,k)+C(n*(m-2),k))%mod;
        s[3]=2*(C((n-2)*(m-1),k)+C((n-1)*(m-2),k))%mod;
        s[4]=C((n-2)*(m-2),k)%mod;
        return (s[0]-s[1]+s[2]-s[3]+s[4]+mod)%mod;
    }
	long long C(long long n,long long m)//组合数公式
    {
        if(m>n) return 0;
		long long a=f[m]*f[n-m]%mod;
		long long nn=mod-2;
		long long ans=1;
        while(nn){
            if(nn&1) ans=ans*a%mod;
            a=a*a%mod;
            nn>>=1;
        }
        return f[n]*ans%mod;
    }
};

复杂度分析

时间复杂度：该算法的时间主要是花在了计算组合数上，计算组合数的时间复杂度为$O(n)$
空间复杂度：在设计组合数时利用了额外的存储空间，空间复杂度为$O(k)$

方法二

思路分析

上面的方法中也可使用动态规划的办法先求出组合数，并将组合数放在二维数组中，因此设置一个大小为$(n*m)*k$的二维数组，存储组合数，利用组合数的递推公式 $C_{m}^{n}=C_{m}^{n-1}+C_{m-1}^{n-1}$ ,利用动态规划的思想自下而上计算组合数存储在二维数组中。

核心代码

class Solution {
public:
    /**
     *
     * @param n int整型
     * @param m int整型
     * @param k int整型
     * @return int整型
     */
    const int mod=1e9+7;
    #define MAXN 1001
	long long res[MAXN][MAXN] = { 0 };//用于存储组合数
	void C(int n,int m,int k) {
		for (int i = 1; i <= n*m; i++) {
			res[i][1] = i;
		}
		for (int i = 1; i <= n*m; i++) {
			for (int j = 2; j <= k; j++) {
				res[i][j] = (res[i - 1][j] + res[i - 1][j - 1])%mod;
				
			}
		}
	}
    
    
    int solve(int n, int m, int k) {
        C(n,m,k);
        vector<long long> s(5,0);
        s[0]=res[n*m][k]%mod;
        s[1]=2*(res[(n-1)*m][k]%mod+res[n*(m-1)][k]%mod)%mod;
        s[2]=(4*res[(n-1)*(m-1)][k]%mod+res[(n-2)*m][k]%mod+res[n*(m-2)][k]%mod)%mod;
        s[3]=2*(res[(n-2)*(m-1)][k]%mod+res[(n-1)*(m-2)][k]%mod)%mod;
        s[4]=res[(n-2)*(m-2)][k]%mod;
        return (s[0]-s[1]+s[2]-s[3]+s[4]+mod)%mod;
    }
};

复杂度分析