ABC285GH题解
G
可以把 \(2\) 的覆盖视作一对匹配，显然在网格图上是二分图。
那么对于 \(?\) 的处理，是可以匹配也可以不匹配，\(2\) 是必须匹配。
所以做上下界网络流即可，复杂度 \(O((nm)^{1.5})\)。
H
题意可以转化为，有 \(k\) 种不同颜色的球放进 \(n\) 个区分的箱子里，每个箱子不可为空，且不可每种颜色都是偶数个。
为空的限制可以包含在第二个限制中。
考虑如果让每一个合法，把生成函数卷积，那么对每个盒子都需要钦定一些颜色必须选奇数，然后这个难以进一步推导。
所以反过来，考虑钦定一些不合法然后容斥。
不合法当且仅当所有都选的偶数，那么生成函数为
\[1+x^2+x^4+...=\frac 1{1-x^2} \]没有要求的生成函数为
\[1+x+x^2+...=\frac 1{1-x} \]枚举不合法的个数写出容斥式子
\[\sum_{i=0}^n(-1)^i\binom n i\prod_{j=1}^k[x^{E_j}]\bigg(\frac 1 {1-x^2}\bigg)^i\bigg(\frac{1}{1-x}\bigg)^{n-i} \]后面的多项式递推就是做前缀和和差分，都是容易的。
所以总共可以做到 \(O(n^2)\) 的复杂度。
标签：frac,题解,ABC285GH,合法,匹配,bigg From： https://www.cnblogs.com/hellojim/p/17060378.html