UVA 11806 Cheerleaders （容斥原理+二进制枚举）

清疚 2022-07-25 16:32 99阅读 0赞

UVA 11806 Cheerleaders （容斥原理+二进制枚举） ：[http://acm.hust.edu.cn/vjudge/contest/view.action?cid=110771\#problem/G][http_acm.hust.edu.cn_vjudge_contest_view.action_cid_110771_problem_G] 传送门：nefu

题目大意：

往一个n\*m的格子内部放k个石子，要求四个边上必须都有，求所有放置石子的方法数。

题目分析：

由于正常去做需要考虑的情况种类数比较多，所以我们反过来考虑。设往一个n\*m的格子中任意存放k个石子的方法数，设为全集S，设集合A表示：第一行没有石子的方法数，集合B表示：最后一行没有石子的方法数，集合C表示：第一列没有石子的方法数，集合D表示：最后一列没有石子的方法数，根据容斥原理，满足题意的方法数共有|S-（A并B并C并D）|，即全集减去第一行或者最后一行或者第一列或者最后一列没有石子的方法数。

此题比较有技巧性的方面还体现在应用了二进制枚举和组合数的打表。

代码实现：

#include <iostream>
    #include <cstdio>
    #include <cstring>
    
    using namespace std;
    const int Mod=1000007;
    
    int c[510][510];
    void Uint()
    {
        memset(c,0,sizeof(c));
        c[0][0]=1;
        for(int i=0;i<=500;i++)
        {
            c[i][0]=1;
            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 main()
    {
        int t,n,m,k;
        int casenum=0;
        Uint();
        scanf("%d",&t);
        while(t--)
        {
            scanf("%d%d%d",&m,&n,&k);
            int sum=0;
            for(int w=0;w<16;w++) //二进制枚举，由于有四个集合，所以要枚举到16
            {
                int b=0,cc=m,r=n;
                if(w&1)
                {
                    b++;
                    cc--;
                }
                if(w&2)
                {
                    b++;
                    cc--;
                }
                if(w&4)
                {
                    b++;
                    r--;
                }
                if(w&8)
                {
                    b++;
                    r--;
                }
                if(b&1)
                {
                    sum=(sum-c[cc*r][k]+Mod)%Mod;
                }
                else
                {
                    sum=(sum+c[cc*r][k])%Mod;
                }
            }
            printf("Case %d: %d\n",++casenum,sum);
        }
        return 0;
    }

[http_acm.hust.edu.cn_vjudge_contest_view.action_cid_110771_problem_G]: http://http://acm.hust.edu.cn/vjudge/contest/view.action?cid=110771#problem/G