首页 > 代码库 > 【递推】【组合数】【容斥原理】UVA - 11806 - Cheerleaders
【递推】【组合数】【容斥原理】UVA - 11806 - Cheerleaders
http://www.cnblogs.com/khbcsu/p/4245943.html
本题如果直接枚举的话难度很大并且会无从下手。那么我们是否可以采取逆向思考的方法来解决问题呢？我们可以用总的情况把不符合要求的减掉就行了。
首先我们如果不考虑任何约束条件，我们可以得出如下结论：
下载我们假定第一行不站拉拉队员的所有的站立方法有A种。最后一行不站拉拉队员的所有的方法有B种。第一列不站拉拉队员的所有的站立方法有C种。最后一列不站拉拉队员的站立方法有D种。
下面我们可以得出最后结果：
#include<cstdio>
using namespace std;
#define MOD 1000007
int C[510][510];
int T,n,m,K;
int main(){
// freopen("uva11806.in","r",stdin);
C[0][0]=1;
for(int i=1;i<=500;++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;
}
}
scanf("%d",&T);
for(int i=1;i<=T;++i){
scanf("%d%d%d",&n,&m,&K);
int ans=C[n*m][K];
ans=(ans+MOD-C[n*(m-1)][K])%MOD;
ans=(ans+MOD-C[n*(m-1)][K])%MOD;
ans=(ans+MOD-C[(n-1)*m][K])%MOD;
ans=(ans+MOD-C[(n-1)*m][K])%MOD;
ans=(ans+C[(n-1)*(m-1)][K])%MOD;
ans=(ans+C[(n-1)*(m-1)][K])%MOD;
ans=(ans+C[(n-2)*m][K])%MOD;
ans=(ans+C[(n-1)*(m-1)][K])%MOD;
ans=(ans+C[n*(m-2)][K])%MOD;
ans=(ans+C[(n-1)*(m-1)][K])%MOD;
ans=(ans+MOD-C[(n-1)*(m-2)][K])%MOD;
ans=(ans+MOD-C[(n-1)*(m-2)][K])%MOD;
ans=(ans+MOD-C[(n-2)*(m-1)][K])%MOD;
ans=(ans+MOD-C[(n-2)*(m-1)][K])%MOD;
ans=(ans+C[(n-2)*(m-2)][K])%MOD;
printf("Case %d: %d\n",i,ans);
}
return 0;
}
【递推】【组合数】【容斥原理】UVA - 11806 - Cheerleaders
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。