基础算法题——牛牛的棋盘（容斥原理）

青旅半醒 2023-03-01 08:59 6阅读 0赞

> 容斥原理：  
> 一种计数方法。先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复。

#### 题目 ####

[牛客网][Link 1]  
牛牛最近在家里看到一个棋盘，有 n \* m 个格子，在棋盘旁边还放着 k 颗棋子，牛牛想把这 k 颗棋子全部放在 n \* m 的棋盘上，但是有一个限制条件：棋盘的第一行、第一列、最后一行和最后一列都必须有棋子。牛牛想知道这样的棋子放法到底有多少种，答案需要对1e9+7取模。

示例1  
输入  
2,3,1  
输出  
0

说明  
就1颗棋子，所以无法满足条件。

示例2  
输入  
2,2,2  
输出  
2

说明  
我们可以把第1颗棋子放在左上角，第2颗棋子放在右下角；也可以把第1颗棋子放在右上角，第2颗棋子放在左下角。故而有2种放法。  
备注:  
2<=n,m<=30; 1<=k<=1000

--------------------

##### 解题思路 #####

题意清晰明了，但是若直接求第一行、第一列、最后一行和最后一列都必须有棋子的情况数，我们会发现要考虑的情况很多，例如：加入棋子在左上方角上，那么第一行、第一列可以不必再放棋子，那最后一行、最后一列又该如何放棋子呢？问题看起来相当复杂。

**利用容斥原理**  
将计算出棋盘所有情况，再减去不符合条件的情况数，最终结果就是符合条件的情况数。  
由于每种情况下的条件具有叠加的效果，不符合条件的情况数的确定成为了难点。

举例说明  
假设求下图圆所圈中的范围S  
S = SA \+ SB \+ SC \- SBC \- SAB \- SAC \+ SABC  
![思维导图][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70]

--------------------

##### 实现代码 #####

#include<stdio.h>
    #include<memory.h>
    long long f[1010][1010];
    const long long mod = 1e9+7;
    
    void init(int n){ 
    	memset(f, 0, sizeof(f));
    	for(int i=1; i<=n; i++){ 
    		f[i][1] = i;
    	}
    	for(int i=1; i<=n; i++)
    	for(int j=2; j<=n; j++)
    		f[i][j] = (f[i-1][j-1] + f[i-1][j]) % mod;
    	return;
    }
    
    int solve(int n, int m, int k){ 
    	init(n*m);
    	int ans = f[n*m][k] % mod;						// f[n*m][k]：每个位置都可以放 
    	ans = (ans - 2 * f[n*(m-1)][k] + mod) % mod;	// f[n*(m-1)][k]：左列或右列不可放 
    	ans = (ans - 2 * f[(n-1)*m][k] + mod) % mod;	// f[(n-1)*m][k]：上行或下行不可放 
    	ans = (ans + 4 * f[(n-1)*(m-1)][k] + mod) % mod;//f[(n-1)*(m-1)][k]：一行与一列不可放 
    	ans = (ans + f[n*(m-2)][k] + mod) % mod;		// f[n*(m-2)][k]：左右列不可放 
    	ans = (ans + f[(n-2)*m][k] + mod) % mod;		// f[(n-2)*m][k]：上下行不可放 
    	ans = (ans - 2 * f[(n-2)*(m-1)][k] + mod) % mod;//f[(n-2)*(m-1)][k]：上下行与一列不可放 
    	ans = (ans - 2 * f[(n-1)*(m-2)][k] + mod) % mod;//f[(n-1)*(m-2)][k]：左右列与一行不可放 
    	ans = (ans + f[(n-2)*(m-2)][k] + mod) % mod;	//f[(n-2)*(m-2)][k]：左右列与上下行不可放 
    	return ans;
    }
    
    
    int main(){ 
    	int n, m, k, ans=0;
    	scanf("%d,%d,%d", &n, &m, &k);
    	printf("%lld", solve(n,m,k));
    	return 0;
    }

若文章对你有帮助，给我个赞好吧：)

[Link 1]: https://ac.nowcoder.com/acm/problem/204568
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70]: /images/20230209/bd0cdb89ae0645e78cdb8121f7d4f62f.png