Uva 11806 拉拉队

题目链接：https://uva.onlinejudge.org/external/118/11806.pdf

题意：

n行m列的矩阵上放k个棋子，其中要求第一行，最后一行，第一列，最后一列必须要有。有多少种放法；

分析：

要是没有那个条件，就直接是C(n*m,k)了，其实也可以转换过来。

设满足“第一行没有棋子”的方案数为A，“最后一行没有棋子”的方案数B，C,D；

然后用容斥原理可以求出。

这里用二进制表示这16种组合；满足偶数个条件为+；

#include <bits/stdc++.h>

using namespace std;

const int MOD = 1000007;
const int maxn = 500;
int C[maxn+10][maxn+10];

int main()
{
    memset(C,0,sizeof(C));
    C[0][0] = 1;

    for(int i=0;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;
    cin>>t;
    int kase = 1;
    while(t--) {
        int n,m,k,sum = 0;
        cin>>n>>m>>k;
        for(int S=0;S<16;S++) {
            int b = 0;
            int r = n;
            int c = m;
            if(S&1) {r--;b++;}
            if(S&2) {r--;b++;}
            if(S&4) {c--;b++;}
            if(S&8) {c--;b++;}
            if(b&1) sum = (sum + MOD - C[r*c][k]) % MOD;
            else sum = (sum + C[r*c][k])%MOD;
        }
        printf("Case %d: %d
",kase++,sum);
    }

    return 0;
}