atdpo 状压求二分图完备匹配数

· · 个人记录

设 f(S) 表示匹配完集合 S 的方案数，最后一个匹配的左点编号就是 S 的模，那么这最后一个点可以和一个右点匹配，当且仅当这两点之间有边且这个右点在 S 中。

然后就好了。可以推测这个问题应该是 NP 难的。