题解 | #牛牛的棋盘#

牛牛的棋盘

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

复杂度分析

时间复杂度：时间主要用于组合数的计算，设置了两层循环，时间复杂度为$O(n*m*k)$
空间复杂度：借助于一个数组存储组合数，空间复杂度为$O(n*m*k)$

全部评论

推荐最新楼层

11-25 15:30

已编辑

麻城理工学校嵌入式软件开发

秋招真的有不焦虑的人吗？

最近又搬回宿舍了，在工位坐不住，写一写秋招起伏不断的心态变化，也算对自己心态的一些思考表演式学习从开始为实习准备的时候就特别焦虑，楼主一开始选择的是cpp后端，但是24届这个方向已经炸了，同时自己又因为本科非92且非科班，所以感到机会更加迷茫。在某天晚上用java写出hello world并失眠一整晚后选择老本行干嵌入式。理想是美好的，现实情况是每天忙但又没有实质性进展，总是在配环境，调工具，顺带还要推科研。而这时候才发现自己一直在表演式学习，徘徊在设想如何展开工作的循环里，导致没有实质性进展。现在看来当时如果把精力专注在动手写而不是两只手端着看教程，基本功或许不会那么差。实习的焦虑5月，楼主...

耶比：哲学上有一个问题，玛丽的房间：玛丽知道眼睛识别色彩的原理知道各种颜色，但是她生活在黑白的房间里，直到有一天玛丽的房门打开了她亲眼看到了颜色，才知道什么是色彩。我现在最大可能的减少对非工作事情的思考，如果有一件事困扰了我，能解决的我就直接做（去哪里或者和谁吵架等等……），解决不了的我就不想了，每一天都是最年轻的一天，珍惜今天吧