http://www.cnblogs.com/khbcsu/p/4245943.html
https://vjudge.net/problem/UVA-11806
本題大致意思是講：給定一個廣場，把它分為M行N列的正方形小框?，F(xiàn)在給定有K個拉拉隊員，每一個拉拉隊員需要站在小框內(nèi)進(jìn)行表演。但是表演過程中有如下要求：
（1）每一個小框只能站立一個拉拉隊員；
（2）廣場的第一行，最后一行，第一列，最后一列都至少站有一個拉拉隊員；
（3）站在廣場的四個角落的拉拉隊員可以認(rèn)為是同時占據(jù)了一行和一列。
2.思路分析：
本題如果直接枚舉的話難度很大并且會無從下手。那么我們是否可以采取逆向思考的方法來解決問題呢？我們可以用總的情況把不符合要求的減掉就行了。
首先我們?nèi)绻豢紤]任何約束條件，我們可以得出如下結(jié)論：
下載我們假定第一行不站拉拉隊員的所有的站立方法有A種。最后一行不站拉拉隊員的所有的方法有B種。第一列不站拉拉隊員的所有的站立方法有C種。最后一列不站拉拉隊員的站立方法有D種。
下面我們可以得出最后結(jié)果：
下面問題來了我們?nèi)绾卫么a實現(xiàn)容斥原理呢？我們可以借用離散數(shù)學(xué)的最大項和最小項知識結(jié)合與運(yùn)算來判斷每一項的特征。比如說，含A的和1進(jìn)行與運(yùn)算。含B的與2進(jìn)行與運(yùn)算。含C的和4進(jìn)行與運(yùn)算。含D的和8進(jìn)行與運(yùn)算。
然后對于每一種狀態(tài)，我們利用數(shù)字0-15來代替。
在進(jìn)行這些工作之前，我們還要進(jìn)行基礎(chǔ)性工作，數(shù)據(jù)初始化和打表。
對于如何打表，我們可以采取組合數(shù)公式的遞推式進(jìn)行。打表過程中一定要注意邊界問題的處理，要不極容易出錯。
#include<stdio.h>
#include<algorithm>
#include <string.h>
using namespace std;
#define maxn 500
typedef long long LL;
int c[maxn+10][maxn+10];
const int mod =1000007;
int main()
{
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]+c[i-1][j-1])%mod;
}
}
int t;
scanf("%d",&t);
for(int cas=1;cas<=t;cas++)
{
int n,m,k,sum=0;
scanf("%d%d%d",&n,&m,&k);
for(int i=0;i<16;i++)
{
int r=n,w=m,b=0;
if(i&1) {r--;b++;}
if(i&2) {r--;b++;}
if(i&4) {w--;b++;}
if(i&8) {w--;b++;}
if(b&1) sum=(sum-c[r*w][k]+mod)%mod;
else sum=(sum+c[r*w][k])%mod;
}
printf("Case %d: %d\n",cas,sum);
}
}
