首页 > 代码库 > UVA 11806 - Cheerleaders(数论+容斥原理)
UVA 11806 - Cheerleaders(数论+容斥原理)
题目链接:11806 - Cheerleaders
题意:在一个棋盘上,要求四周的四行必须有旗子,问有几种摆法。
思路:直接算很容易乱掉,利用容斥原理,可知AUBUCUD = |A| + |B| + |C| + |D| - |AB| - |BC| - |AC| - |AD| - |BD| - |CD| + |ABC| + |ABD| + |ACD| + |BCD| - |ABCD|
由此利用位运算去计算即可
代码:
#include <stdio.h> #include <string.h> const int MOD = 1000007; const int N = 505; int t, n, m, k, C[N][N]; int main() { C[0][0] = 1; for (int i = 0; i < N; 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 cas = 0; scanf("%d", &t); while (t--) { int sum = 0; scanf("%d%d%d", &n, &m, &k); for (int s = 0; s < 16; s++) { int count = 0, r = n, c = m; if (s&1) {count++; r--;} if (s&2) {count++; r--;} if (s&4) {count++, c--;} if (s&8) {count++, c--;} if (count&1) sum = (sum - C[r * c][k] + MOD) % MOD; else sum = (sum + C[r * c][k]) % MOD; } printf("Case %d: %d\n", ++cas, sum); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。