1)题目意思
有 N 个男生、N 个女生。给你一个 N×N 的 0/1 矩阵 a[i][j]:
* a[i][j]=1 表示男 i 可以和女 j 配对
* a[i][j]=0 表示不能配对
要把所有人配成 N 对(每个男生、每个女生都恰好出现一次),问一共有多少种配对方法,答案对 1e9+7 取模。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2)思路解析(状态压缩 DP:计数完美匹配)
N<=21,可以用二进制 mask 表示“哪些女生已经被配走”。
按男生顺序一个个匹配:
* 当 mask 里有 k 个 1,说明已经给前 k 个男生配完了女生
* 下一个要处理的男生编号就是 k+1
定义:
* dp[mask]:当已经使用的女生集合为 mask 时的配对方案数(默认男生按顺序处理)
转移:
* 设当前要处理的男生为 i = popcount(mask) + 1
* 枚举一个还没用过的女生 j
* 如果 a[i][j]=1,就可以配对
* dp[mask | (1<<j)] += dp[mask]
初始:
* dp[0]=1(还没配任何人)
答案:
* dp[(1<<N)-1]
复杂度:
* 状态数 2^N,N=21 时约 200 万
* 每个状态最多枚举 N 个女生
* 总体可过
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
3)代码