D - Cheerleaders

题目链接：https://vjudge.net/contest/154063#problem/D

题目大意：

给你一个 n∗m 的方格，现在有 k 个相同石子，我们要将这 k 个石子完全放入 n∗m 中，

要求的是第一行、第一列、最后一行和最后一列中必须有石子，求的是方案数。

解题思路： 
我们来分析一下这个题目，因为题目中要求的是第一行、第一列、最后一行和最后一列中必须有石子，那么我们现在应该从反面考虑也就是利用容斥原理解决这个问题，这个是很容易想到的，那么现在我们设 4 个事件: 
A：表示的是第一行中没有石子的方案数 
B：表示的是第一列中没有石子的方案数 
C：表示的是最后一行中没有石子的方案数 
D：表示的是最后一列中没有石子的方案数 
那么我们要求的方案数就是： 
|A∪B∪C∪D|=|A|+|B|+|C|+|D|−|A∩B|−|A∩C|−|A∩D|−|B∩C|−|B∩D|−|C∩D|+|A∩B∩C|+|A∩B∩D|+|A∩C∩D|+|B∩C∩D|−|A∩B∩C∩D|
然后利用二进制枚举总的状态就可以了。

#include
#include
#include
using namespace std;
const int MOD=;
const int MAX=;
int c[MAX][MAX];
void plzh()
{
for(int i=;i<=;i++)
{
c[i][]=;
c[i][i]=;
}
for(int i=; i<=; i++)
{
for(int j=; j<i; j++)
{
c[i][j]=(c[i-][j-]+c[i-][j])%MOD;
}
}
}
int main()
{
plzh();
int t,s=;
int n,m,k;
scanf("%d",&t);
while(t--)
{
s++;
scanf("%d%d%d",&n,&m,&k);
int sum=;
for(int i=; i<; i++)
{
int x=n,y=m,cnt=;
if(i&)
{
x--;
cnt++;
}
if(i&)
{
y--;
cnt++;
}
if(i&)
{
x--;
cnt++;
}
if(i&)
{
y--;
cnt++;
}
if(cnt&)
sum= ((sum - c[x*y][k])%MOD+MOD)%MOD;
else sum=(sum+c[x*y][k])%MOD;
}
printf("Case %d: %d\n",s,sum);
}
return ;
}