【学习笔记】[THUWC2017]随机二分图

既然不讲课，于是又在做题中度过了，看来变化确实是人类的天敌。

这题。。。我不好说。

考虑怎么算一个完美匹配对答案的贡献。发现如果每条边一个编号的话，假设有$K$个种类，贡献就是12K\\frac{1}{2^K}2K1​，限制是有些编号最多只能出现一次。

如果没有这个限制呢？感觉非常离谱，因为暴力算完美匹配的复杂度是O(22n)O(2^{2n})O(22n)。

怎么改进呢？神奇的地方来了。我们可以将其分成前n2\\frac{n}{2}2n​和后n2\\frac{n}{2}2n​个节点，然后做交叉匹配，这样点的数目就只有$n$个了 。算一下发现最后统计答案的复杂度也能够通过。

那么直接大力状压即可，说直白点就是把同一组里的边同时拿来转移。

复杂度O(2nn2)O(2^nn^2)O(2nn2)，估摸着能过。

代码咕了。