当前位置: 代码迷 >> 综合 >> UVa11806 Cheerleaders(容斥原理)
  详细解决方案

UVa11806 Cheerleaders(容斥原理)

热度:50   发布时间:2024-01-16 13:32:11.0

题意:

给出一个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;
}


  相关解决方案