首页 > 其他 > 详细

uva11806 Cheerleaders

时间:2017-08-26 15:33:30      阅读:272      评论:0      收藏:0      [点我收藏+]

题目大意:

n行m列网格放k个石子。有多少种方法?要求第一行,第一列,最后一行,最后一列必须有石子。

/*
    利用容斥原理。可以转到求“第一行、第一列、最后一行、最后一列没有石子”的方案数。
    枚举各个集合的组合时可以借助二进制进行枚举
*/
#include<iostream>
#include<cstdio>
using namespace std;
#define mod 1000007
int t,n,m,k,c[510][510],Case;
int main(){
    for(int i=0;i<=500;i++){
        c[i][0]=c[i][i]=1;
        for(int j=1;j<i;j++)
            c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
    }
    scanf("%d",&t);
    while(t--){
        Case++;
        scanf("%d%d%d",&n,&m,&k);
        int ans=0;
        for(int i=0;i<16;i++){
            int b=0,n1=n,m1=m;
            if(i&1){n1--;b++;}
            if(i&2){n1--;b++;}
            if(i&4){m1--;b++;}
            if(i&8){m1--;b++;}
            if(b&1)ans=(ans+mod-c[n1*m1][k])%mod;
            else ans=(ans+c[n1*m1][k])%mod;
        }
        printf("Case %d: %d\n",Case,ans);
    }
}

 

uva11806 Cheerleaders

原文:http://www.cnblogs.com/thmyl/p/7435308.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!