牛牛的棋盘 解题报告

由于题目中要求的是第一行、第一列、最后一行和最后一列中必须有棋子，那么我们从正面考虑情况特别复杂，所以
我们可以从反面来考虑这个问题，那么现在我们假设 4 个事件:
事件A：表示第一行中没有棋子的放法方案数
事件B：表示第一列中没有棋子的放法方案数
事件C：表示最后一行中没有棋子的放法方案数
事件D：表示最后一列中没有棋子的放法方案数
那么根据容斥原理，我们所求答案如下：
那么我们就可以根据上述所求，先预处理一下组合数的计算，不要忘记取模，然后利用二进制枚举各个集合，奇减偶加，得到结果即可。
代码如下：

const int MAXN = 1e3+5;
const int MOD = 1e9+7;
int dp[MAXN][MAXN];
void Init(){
    for(int i=0; i<MAXN; i++)
        dp[i][0] = dp[i][i] = 1;
    for(int i=1; i<MAXN; i++)
        for(int j=1; j<=i; j++)
            dp[i][j] = (dp[i-1][j-1]+dp[i-1][j]) % MOD;
}
class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @param m int整型 
     * @param k int整型 
     * @return int整型
     */
    int solve(int n, int m, int k) {
        // write code here
        Init();
        int ans = 0;
        //16是2^4，一共4种情况，每种情况都有0和1两种状态，所以一共是2^4种状态
        for(int i=0; i<16; i++){
            int cnt = 0, c = n, r = m;
            if(i & 1) { cnt++; c--; }
            if(i & 2) { cnt++; r--; }
            if(i & 4) { cnt++; c--; }
            if(i & 8) { cnt++; r--; }
            if(cnt & 1) ans = (ans-dp[r*c][k]+MOD)%MOD;
            else ans = (ans+dp[r*c][k])%MOD;
        }
        return ans;
    }
};