1 条题解
-
0
[O] Matching(dp_o)题解
题意简述
男 女, 表示可配对。求完美匹配方案数 。
思路
关键想法:按女士顺序决策,用 bitmask 记录男士占用情况
如果按"男士/女士各挑"的二维状态,需要 ,不可行。注意到:按女士编号 依次配对时,前 位女士已经用掉了恰好 位男士,所以只需记录"哪些男士被占用"。
状态 = 用 mask 中的男士与前 位女士配对的方案数。
转移:设当前要配第 位女士(0 起),枚举 mask 中的男士 :
$$f_{\text{mask}} \mathrel{+}= f_{\text{mask} \setminus \{m\}} \quad \text{当 } a_{w,m} = 1.$$答案 。
为什么正确
按女士顺序配对避免了重复计数:每个完美匹配都唯一对应一条"第 位女士选谁、第 位选谁…"的路径。
复杂度
时间 , 时约 ,可过;空间 。
参考代码
#include <cstdio> #include <vector> using namespace std; const long long MOD = 1000000007LL; int main() { int n; scanf("%d", &n); vector<vector<int>> a(n, vector<int>(n)); for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) scanf("%d", &a[i][j]); int full = 1 << n; vector<long long> f(full, 0); f[0] = 1; for (int mask = 1; mask < full; mask++) { int w = __builtin_popcount(mask) - 1; long long s = 0; for (int m = mask; m; m &= m - 1) { int man = __builtin_ctz(m); if (a[w][man]) s += f[mask ^ (1 << man)]; } f[mask] = s % MOD; } printf("%lld\n", f[full - 1]); return 0; }易错点
w的取值:popcount(mask) - 1,因为 mask 表示"已占用,用于前 popcount 位女士",当前正在配第 popcount-1 位(0 起)。- 每次
s累加后要取模,否则 大数会溢出。 - 状态数组 B MB,可接受;用
int则 8 MB。 - 全 0 矩阵的答案是 (样例 3 的 )。
数据说明
共 17 组:4 组官方样例(含 的 ); 的 ; 全 1 与单位阵; 随机; 随机; 的全 1 矩阵(答案 )与随机矩阵(满规模)。
- 1
信息
- ID
- 24
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 6
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者