UVa11806 Cheerleaders(容斥原理)

本文主要是介绍UVa11806 Cheerleaders(容斥原理)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：

给出一个n*m的棋盘，在上面放k个棋子，求第一行，第一列，最后一行，最后一列每个都有棋子的组合数。

要点：

简单的容斥原理，对第一行，第一列，最后一行，最后一列没有棋子进行容斥，这样最后减去即可。注意进行容斥时如果是相减的可能出现负数，所以在前面+MOD。

#include<iostream>
#include<cstring>
#include<algorithm>
#define MOD 1000007
using namespace std;
const int K=510;
int C[K][K];void init()
{memset(C,0,sizeof(C));for(int i=0;i<K;i++)//注意这里下标不能越界 C[i][0]=1;for(int i=1;i<K;i++)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,kase=1;init();scanf("%d",&t);while(t--){scanf("%d%d%d",&n,&m,&k);int sum=0;for(int i=1;i<16;i++)//注意这里i从1开始 {int r=n,c=m,b=0;//b表示集合中的元素个数 if(i&1) r--,b++;if(i&2) r--,b++;if(i&4) c--,b++;if(i&8) c--,b++;if(b%2==1)//容斥原理，奇加偶减 sum=(sum+C[r*c][k])%MOD;elsesum=(sum+MOD-C[r*c][k])%MOD;}int ans=(C[n*m][k]-sum+MOD)%MOD;//总数减去不可能值，注意相减可能是负数，所以必须+MOD printf("Case %d: %d\n",kase++,ans);}return 0;
}

这篇关于UVa11806 Cheerleaders(容斥原理)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---