首页 > 代码库 > UVa 11806 拉拉队（容斥原理）
UVa 11806 拉拉队（容斥原理）
https://vjudge.net/problem/UVA-11806
题意：
在一个m行n列的矩形网格里放k个相同的石子，有多少种方法？每个格子最多放一个石子，所有石子都要用完，并且第一行、最后一行、第一列、最后一列都得有石子。
思路：
如果考虑各种情况的话很复杂，设满足第一行没有石子的方案集为A，最后一行没有石子的方案集为B，第一列没有石子的方案集为C，最后一列没有石子的方案集为D，全集为S。
一个容斥原理的公式就可以解答出来，用二进制来枚举方案集的组合。
1 #include <iostream> 2 #include <cstring> 3 #include <algorithm> 4 #include <vector> 5 #include <queue> 6 #include <cmath> 7 using namespace std; 8 9 const int mod = 1000007;10 const int maxn = 500+5;11 12 int c[maxn][maxn];13 14 void init()15 {16 for (int i = 0; i <= maxn; i++)17 {18 c[i][0] = c[i][i] = 1;19 for (int j = 1; j < i; j++) c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;20 }21 }22 23 int main()24 {25 //freopen("D:\\input.txt", "r", stdin);26 int T;27 int kase = 0;28 int n, m, k;29 scanf("%d", &T);30 init();31 while (T--)32 {33 scanf("%d%d%d", &n, &m, &k);34 int sum = 0;35 for (int S = 0; S<16; S++)36 {37 //S=0时就相当于计算c[n*m][k],不考虑条件时的所有方法数38 int b = 0, row = n, col = m;39 if (S & 1) { row--; b++; }40 if (S & 2) { row--; b++; }41 if (S & 4) { col--; b++; }42 if (S & 8) { col--; b++; }43 if (b & 1) sum = (sum + mod - c[row*col][k]) % mod;44 else sum = (sum + c[row*col][k]) % mod;45 }46 printf("Case %d: %d\n", ++kase, sum);47 }48 return 0;49 }
UVa 11806 拉拉队（容斥原理）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。