首页 > 代码库 > UVAL 11806 Cheerleaders 容斥原理
UVAL 11806 Cheerleaders 容斥原理
1.题意描述
本题大致意思是讲:给定一个广场,把它分为M行N列的正方形小框。现在给定有K个拉拉队员,每一个拉拉队员需要站在小框内进行表演。但是表演过程中有如下要求:
(1)每一个小框只能站立一个拉拉队员;
(2)广场的第一行,最后一行,第一列,最后一列都至少站有一个拉拉队员;
(3)站在广场的四个角落的拉拉队员可以认为是同时占据了一行和一列。
2.思路:
本题如果直接枚举的话难度很大并且会无从下手。那么我们是否可以采取逆向思考的方法来解决问题呢?我们可以用总的情况把不符合要求的减掉就行了。
首先我们如果不考虑任何约束条件,我们可以得出如下结论:
下载我们假定第一行不站拉拉队员的所有的站立方法有A种。最后一行不站拉拉队员的所有的方法有B种。第一列不站拉拉队员的所有的站立方法有C种。最后一列不站拉拉队员的站立方法有D种。
下面我们可以得出最后结果:
四种元素,一共有十六种状态,用0~15来枚举每一种状态。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define M 1000007 #define ma 505 int a[ma][ma]; void zuhe()/ { memset(a,0,sizeof(a)); a[0][0]=1; for(int i=1;i<ma;i++) { a[i][0]=a[i][i]=1; for(int j=1;j<i;j++) a[i][j]=(a[i-1][j-1]+a[i-1][j])%M; } } int main() { zuhe(); int t; scanf("%d",&t); for(int g=1;g<=t;g++) { int n,m,k; int sum=0; scanf("%d%d%d",&n,&m,&k); for(int i=0;i<16;i++) { int r=n,c=m,b=0; if(i&1) {r--;b++;} if(i&2) {r--;b++;} if(i&4) {c--;b++;} if(i&8) {c--;b++;} if(b&1) sum=(sum+M-a[r*c][k])%M;//奇数个元素 else sum=(sum+a[r*c][k])%M; } printf("Case %d: %d\n",g,sum); } return 0; }
UVAL 11806 Cheerleaders 容斥原理
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。