UVA11806 容斥定理

科技前沿 • 2025-04-09 11:57 • 阅读 49

大家好，我是讯享网，很高兴认识大家。

UVA11806【拉拉队】Cheerleaders

.题意描述

本题大致意思是讲：给定一个广场，把它分为M行N列的正方形小框。现在给定有K个拉拉队员，每一个拉拉队员需要站在小框内进行表演。但是表演过程中有如下要求：

（1）每一个小框只能站立一个拉拉队员；

（2）广场的第一行，最后一行，第一列，最后一列都至少站有一个拉拉队员；

（3）站在广场的四个角落的拉拉队员可以认为是同时占据了一行和一列。

讯享网

要注意空白的地方也是每一个单元格放一个人，也是可以构成组合数的

analize：

组合数问题用容斥定理解决，假设从n*m里面挑选出k个单元格，这是所有的情况，但是直接去找满足题意的情况是不太好模拟的，于是可以从逆向的角度求，假设情况A代表第一行全没有人的情况组合数，B代表最后一行全没有人的情况组合数，同理C代表最左边全部没有人的情况，D代表最右边没有人的情况数，那么AB代表第一行和最后一行都没有人的情况。。。。。依次类推，他们之间的关系就是由容斥定理连接

#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> using namespace std; typedef long long ll; #define rep(i,a,b) for(int i=a;i<=b;i++) const ll INF=0x3f3f3f3f3f3f3f3f; const int N=1e6+7; const int MOD= ; int c[500][500]; void Init(){//组合数打表 c[0][0]=1; rep(i,1,400){ c[i][0]=1; rep(j,1,i) c[i][j]=(c[i-1][j]+c[i-1][j-1])%MOD; } } int main() { #ifndef ONLINE_JUDGE freopen("in.txt","r",stdin); #endif // ONLINE_JUDGE Init(); int T; int n,m,k; scanf("%d",&T); rep(o,1,T) { int ans=0; scanf("%d%d%d",&n,&m,&k); rep(s,0,15){//因为总共有16种情况，每一种情况赋予一定的编号 int row=n,cal=m,b=0;//b是统计当前的单双数的（不是s） if(s&1) b++,row--; if(s&2) b++,cal--; if(s&4) b++,row--; if(s&8) b++,cal--; if(b&1) ans=(ans+MOD-c[row*cal][k])%MOD;//单数的情况 else ans=(ans+c[row*cal][k])%MOD;//双数的情况 } printf("Case %d: %d\n",o,ans); } return 0; }

讯享网

UVA11806 容斥定理

相关推荐