链接：https://ac.nowcoder.com/acm/contest/6219/C
来源：牛客网
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
牛牛最近在家里看到一个棋盘，有nm个格子，在棋盘旁边还放着k颗棋子，牛牛想把这k颗棋子全部放在nm的棋盘上，但是有一个限制条件：棋盘的第一行、第一列、最后一行和最后一列都必须有棋子。牛牛想知道这样的棋子放法到底有多少种，答案需要对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
题目大意：
给出n*m的棋盘和k个旗子，第一行，最后一行，第一列和最后一列都必须有旗子，求放置方案数。
解题思路：
组合数学+容斥原理，正难则反的思想， 容斥原理可以描述如下：要计算几个集合并集的大小，我们要先将所有单个集合的大小计算出来，然后减去所有两个集合相交的部分，再加回所有三个集合相交的部分，再减去所有四个集合相交的部分，依此类推，一直计算到所有集合相交的部分。先求总方案，然后再减去第一行没有旗子，最后一行没有旗子，加上第一行最后一行都没有旗子(因为前面减重了)…第一列和最后一列没有旗子的即可。总方案C nm k 第一行或最后一行C (n-1)m k 第一列或最后一列C n(m-1) k 因为每种只有01放和不放两个状态，可以用4个for循环，也可以状态压缩，把每个状态压缩成01，放就是1，不放就是0，那么0000-1111即1-15即可枚举所有可能的状态。奇加偶减，用杨辉三角打组合数表，然后再计算即可。AC代码：
class Solution {
public:
int mod=1e9+7;
long long f[1500][1500];
void init()//打组合数表
{
for(int i=0;i<1500;i++)
{
f[i][i]=1;
f[i][0]=1;
}
for(int i=1;i<1500;i++)
for(int j=1;j<i;j++)
f[i][j]=(f[i-1][j]+f[i-1][j-1])%mod;
}
int solve(int n, int m, int k) {
// write code here
init();
long long ans=0;
for(int i=0;i<16;i++)//状压
{
int c=(i&1)+((i>>1)&1);
int h=((i>>2)&1)+((i>>3)&1);
int x=c+h;
if(x&1)
ans=(ans-f[(n-c)*(m-h)][k]+mod)%mod;//总方案-奇数没放的剩下的就是放的
else
ans=(ans+f[(n-c)*(m-h)][k]+mod)%mod;//偶数个要加回来
}
return ans;
}
};