首页 > 代码库 > UVa 11806 Cheerleaders
UVa 11806 Cheerleaders
题意：m行n列的矩形网格放k个相同的石子，要求第一行最后一行第一列最后一列都必须有石子，问有多少种放法
A为第一行没有石子的方案数，BCD依此类推，全集为S
如果没有任何要求的话，放法数应该是C(rc, k)
解法中利用容斥原理来解
所求的方案就是在S中但不在ABCD中任何一个的方案即：S - |A∪B∪C∪D|
而|A∪B∪C∪D| = |A| + |B| + |C| + |D| - |A∩B| - |A∩C| - |A∩D| - |B∩C| - |B∩D| - |C∩D|
+ |A∩B∩C| + |A∩B∩D| + |A∩C∩D| + |B∩C∩D| - |A∩B∩C∩D|
1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 using namespace std; 6 7 const int MOD = 1000007; 8 const int maxn = 500; 9 int Co[maxn + 10][maxn + 10];10 11 int main(void)12 {13 #ifdef LOCAL14 freopen("11806in.txt", "r", stdin);15 #endif16 17 memset(Co, 0, sizeof(Co));18 for(int i = 0; i <= maxn; ++i)19 Co[i][0] = Co[i][i] = 1;20 for(int i = 2; i <= maxn; ++i)21 for(int j = 1; j < i; ++j)22 Co[i][j] = (Co[i-1][j-1] + Co[i-1][j]) % MOD;23 int T;24 scanf("%d", &T);25 for(int kase = 1; kase <= T; ++kase)26 {27 int n, m, k, sum = 0;28 scanf("%d%d%d", &n, &m, &k);29 for(int S = 0; S < 16; ++S)30 {31 int b = 0, r = n, c = m;32 if(S & 1) { ++b; --r; }33 if(S & 2) { ++b; --r; }34 if(S & 4) { ++b; --c; }35 if(S & 8) { ++b; --c; }36 if(b & 1)37 sum = (sum + MOD - Co[r*c][k]) % MOD;38 else39 sum = (sum + Co[r*c][k]) % MOD;40 }41 printf("Case %d: %d\n", kase, sum);42 }43 return 0;44 }
UVa 11806 Cheerleaders
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。