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 LOCAL
14         freopen("11806in.txt", "r", stdin);
15     #endif
16 
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             else
39                 sum = (sum + Co[r*c][k]) % MOD;
40         }
41         printf("Case %d: %d\n", kase, sum);
42     }
43     return 0;
44 }

代碼君

轉載于:https://www.cnblogs.com/AOQNRMGYXLMV/p/3940468.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/258243.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/258243.shtml
英文地址，請注明出處：http://en.pswp.cn/news/258243.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！