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; } ///end int 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减1 if(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; }