UVA.11806 Cheerleaders (组合数学 容斥原理 二进制枚举)

题意分析

给出n*m的矩形格子，给出k个点，每个格子里面可以放一个点。现在要求格子的最外围一圈的每行每列，至少要放一个点，并且放在角上的点，同时算那个角所在的行和所在的列。不允许剩下点，求总共的方案数量，结果对1000007取模。

数据范围2 ≤ M,N ≤ 20,K ≤ 500。

考虑到要求组合数目，首先就需要预处理500以内的组合数。正向求解可能有些困难，这样考虑：

不管三七二十一，先求解出所有情况的总和，即C(n*m,k)，之后计算出不符合情况的，减去即可。

对于上下左右四条边，设第一行不放的集合为A，最后一行不放的集合为B，第一列不放的集合为C，最后一列不放的集合为D。根据排列组合可以知道，不合法的情况总数有2^4-1 = 15种。对于这15种，就可以用容斥原理求解出来，tot = (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)（这个就是容斥原理）. 共15项，计算之后分别减去即可。

接着对问题转化，第一行不放是什么意思呢？就是选择范围少了一行，即C((m-1)*n,k)。

然后对于容斥求出来的公式，如何进行计算呢？

发现，当所求的集合时奇数个的时候，要从总数中减去(黑体加粗的式子是正号，因为算的是不符合的情况，减去时要整体填一个负号)，例如A，B，C，D四项均是一个集合，而(A∩B∩C∩D)就是四个集合。对于集合个数是偶数个的时候，就要加上。做到这一点，也十分容易，用二进制枚举即可。

代码总览

#include <cstdio>

#include <algorithm>

#include <cstring>

#define nmax 505

using namespace std;

int C[nmax][nmax];

int T;

const int MOD = 1000007;

void init()

{

    memset(C,0,sizeof C);

    C[0][0] = 1;

    for(int i = 1;i<nmax;++i){

        C[i][0] = C[i][i] = 1;

        for(int j = 1;j<nmax;++j){

            C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;

        }

    }

}

int main()

{

    //freopen("in.txt","r",stdin);

    init();

    scanf("%d",&T);

    for(int kase = 1;kase <= T; kase++){

        int n,m,k;

        scanf("%d %d %d",&m,&n,&k);

        int up = 1,down = 2,left = 4,right = 8;

        int ans = 0;

        for(int i = 0;i<16;++i){

            int column = n,line = m,index = 0;

            if(up&i) column--,index++;

            if(down&i) column--,index++;

            if(left&i) line--,index++;

            if(right&i) line--,index++;

            if(index&1){

                ans = (ans - C[column * line][k]) % MOD;

            }else{

                ans = (ans + C[column * line][k] + MOD) % MOD;

            }

        }

        printf("Case %d: ",kase);

        printf("%d\n",ans);

    }

    return 0;

}