本文主要是介绍UVa 11806 Cheerleaders (组合逆向思维||容斥定理)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
11806 - Cheerleaders
Time limit: 2.000 seconds
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2906
【题意】
在一个n*m的区域内放k个棋子，第一排，最后一排，第一列，最后一列一定要放，求一共有多少种方法。
【思路】
正着想重复的情况太多，不妨反着思考。
设ai表示有且仅有i条边上没有放的情况数，我们想要的显然是a1+a2+a3+a4，这就是所有不符合要求的情况，但是同样不好直接计算。
但是有一个方便计算的：设si表示i条边上不能放，而其他的地方随便放的情况数，
则有
同时
解得
a1+a2+a3+a4 = s1-s2+s3-s4
【完整代码】
/*0.012s*/#include<cstdio>
const int mod = 1000007;int c[405][405];int main(void)
{///生成组合数c[0][0] = 1;for (int i = 1; i < 405; i++){c[i][0] = c[i][i] = 1;for (int j = 1; j < i; j++)c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;}///endint t, cas = 0, n, m, k, ans, s1, s2, s3, s4;scanf("%d", &t);while (t--){scanf("%d%d%d", &n, &m, &k);if (n * m < k) ans = 0;else{s1 = (c[n * m - m][k] + c[n * m - n][k]) << 1;s2 = c[n * m - m - m][k] + c[n * m - n - n][k] + (c[n * m - n - m + 1][k] << 2);s3 = (c[n * m - n - m - m + 2][k] + c[n * m - m - n - n + 2][k]) << 1;s4 = c[n * m - m - m - n - n + 4][k];ans = ((c[n * m][k] - s1 + s2 - s3 + s4) % mod + mod) % mod;}printf("Case %d: %d\n", ++cas, ans);}return 0;
}
【容斥定理的解法】
/*0.016s*/#include<cstdio>
const int MOD = 1000007;
const int MAXK = 500;int C[MAXK + 10][MAXK + 10];int main()
{C[0][0] = 1;for (int i = 0; i <= MAXK; ++i){C[i][0] = C[i][i] = 1; // 千万不要忘记写边界条件for (int j = 1; j < i; ++j)C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;}int T;scanf("%d", &T);for (int kase = 1; kase <= T; ++kase){int n, m, k, sum = 0;scanf("%d%d%d", &n, &m, &k);for (int S = 0; S < 16; ++S) // 枚举所有16种“搭配方式”{int b = 0, r = n, c = m; // b用来统计集合的个数，r和c是可以放置的行列数if(S & 1) {r--; b++;} // 第一行没有石头，可以放石头的行数r减1if(S & 2) {r--; b++;}if(S & 4) {c--; b++;}if(S & 8) {c--; b++;}if (b & 1) sum = (sum + MOD - C[r * c][k]) % MOD; // 奇数个条件，做减法else sum = (sum + C[r * c][k]) % MOD; // 偶数个条件，做加法}printf("Case %d: %d\n", kase, sum);}return 0;
}
这篇关于UVa 11806 Cheerleaders (组合逆向思维||容斥定理)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
