题目大意
有一个 n*m 的网格场地，现在把 k 个人放进去，要求满足：
- 四个边都至少有一个人
- 一个格子最多放一个人
- 每个人都要放进去
求有多少种合法的放法——答案对 1e6+7 取模
注：四个角上的人可以看做同时在一行和一列
思路
这道题中计算合法的方案数比较困难，所以我们可以计算出全部的方案数再减去不合法的方案数
不考虑约束条件，单纯地将这些人放进网格中，方案数显然有 $allAnswer=C^k_{mn}$
我们知道有四种因素会导致方案不合法，我们用四个集合表示具有某种因素的不合法方案：
-
$A:$ 第一行没有人
-
$B:$ 最后一行没有人
-
$C:$ 第一列没有人
-
$D:$ 最后一列没有人
于是就可以通过容斥原理计算合法的方案数了： $$ approvedAnswer=allAnswer+A\cup B\cup C\cup D-(A\cup B\cup C+A\cup B\cup D+A\cup C\cup D+B\cup C\cup D)+(A\cup B+A\cup C+A\cup D+B\cup C+B\cup D+C\cup D)-(A+B+C+D) $$ 对于任意一种方案数我们都可以用一个四元组表示这种方案具有哪几个不合法因素，其中每个元素1表示具有这种不合法因素，0表示没有。更进一步的，可以将这个四元组通过状态压缩记录在一个整形中，于是我们只需要通过0到15这16个数就可以遍历所有方案的种类，通过与1，2，4，8进行&运算就可以判断是否具有某种不合法因素。
如果一种方案具有$A$这个不合法因素，那么这种方案其实就是将原来的网格场地消去一行之后所有的方案数，即对于(n-1)*m的场地放k个人的全部方案数——$C^k_{m(n-1)}$，和我们一开始求出的 $allAnswer$ 得到了统一。
上面的公式中，约束条件的个数决定了加减，即满足「偶加奇减」原则。因为 $allAnswer$ 实质上是不受任何不合法条件约束的一种特殊的不合法情况，其不合法因素数是0，所以在&1时结果为0，判断为偶数，于是也要加上——和公式相符，不需要特判。
至此，这道题就做完了。不过还有值得注意的一点：在不合法因素数为奇数，需要减去时，我们需要先累加一个模数在进行减法运算，这样就可以保证在取模意义下结果正确而不会因减法运算后得到负数而导致取模后得到负数，以致答案错误。
代码：
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int mod=1e6+7,maxn=405;
int n,m,k,T;
int c[maxn][maxn],ans;
void init(){//Calculate value of combinatorial number at the very first.
memset(c,0,sizeof(c));
c[0][0]=1;
for(int i=1;i<maxn;i++){
c[i][0]=c[i][i]=1;
for(int j=1;j<i;j++)
c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
}
}
int main(){
init();
scanf("%d",&T);
for(int gameRound=1;gameRound<=T;gameRound++){
ans=0;
scanf("%d%d%d",&n,&m,&k);
for(int gameCase=0;gameCase<16;gameCase++){
int fieldRow=n,fieldColumn=m,situationSummary=0;
if(gameCase&1) fieldRow--,situationSummary++;
if(gameCase&2) fieldRow--,situationSummary++;
if(gameCase&4) fieldColumn--,situationSummary++;
if(gameCase&8) fieldColumn--,situationSummary++;
if(situationSummary&1) ans=(ans+mod-c[fieldRow*fieldColumn][k])%mod;
//Plus "mod" to avoid "ans" becoming a negative.
else ans=(ans+c[fieldRow*fieldColumn][k])%mod;
}
printf("Case %d: %d\n",gameRound,ans);
}
return 0;
}