首页 > 代码库 > [HDOJ 5155] Harry And Magic Box
[HDOJ 5155] Harry And Magic Box
题目链接：HDOJ - 5155
题目大意
有一个 n * m 的棋盘，已知每行每列都至少有一个棋子，求可能有多少种不同的棋子分布情况。答案对一个大素数取模。
题目分析
算法1：
使用容斥原理与递推。
首先，一个 n * m 的棋盘不考虑任何限制时，可能的分布情况为 2^(n*m) ，除去没有棋子的情况，为 2^(n*m) - 1 。
然后，因为所有的 n 行，m 列都有棋子，所以枚举 ii (1 <= ii <= i) ， jj (1 <= jj <= j) 。对于枚举的一组 (ii, jj) ，若 (ii, jj) != (i, j) ，f[i][j] 就是恰好有 i 行 j 列都有棋子的情况数，再乘上在 i 行中选 ii 行 ( C[i][ii] ) ，在 j 列中选 jj 列的情况数( C[j][jj] )，就是在 i * j 的棋盘中，恰好有 ii 行， jj 列有棋子的情况数。(i, j) 的答案 f[i][j] 要减去这个值。
这样就递推出了所有的 f[i][j] 。时间复杂度 O(n^4) 。
注意的问题：组合数用递推来求。 C[i][0] = 1, C[i][j] = C[i-1][j-1] + C[i-1][j]; 进行递推时注意取模之后的数相乘会爆 Int 。
算法2：
代码
算法1
#include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>#include <algorithm>using namespace std;const int MaxN = 50 + 5, Mod = 1000000007;int n, m;int C[MaxN][MaxN], f[MaxN][MaxN], Pow2[MaxN * MaxN];void Init_C() { C[0][0] = 1; for (int i = 1; i <= 50; ++i) { C[i][0] = 1; for (int j = 1; j <= i; ++j) { C[i][j] = C[i - 1][j - 1] + C[i - 1][j]; C[i][j] %= Mod; } } Pow2[0] = 1; for (int i = 1; i <= 2500; ++i) { Pow2[i] = Pow2[i - 1] << 1; Pow2[i] %= Mod; }}typedef long long LL;int main() { Init_C(); for (int i = 1; i <= 50; ++i) { for (int j = 1; j <= 50; ++j) { f[i][j] = Pow2[i * j] - 1; for (int ii = 1; ii <= i; ++ii) { for (int jj = 1; jj <= j; ++jj) { if (ii == i && jj == j) continue; f[i][j] -= (LL)f[ii][jj] % Mod * (LL)C[i][ii] % Mod * (LL)C[j][jj] % Mod; f[i][j] %= Mod; } } f[i][j] = (f[i][j] + Mod) % Mod; } } while (scanf("%d%d", &n, &m) != EOF) { if (n == 0 || m == 0) { printf("1\n"); continue; } printf("%d\n", f[n][m]); } return 0;}
算法2
[HDOJ 5155] Harry And Magic Box
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。