ZJOI2018 树

互异关系容斥即将不等号容斥成等号，对于连通块内的 \(\text{GF}\) 形式即为 \(\ln(x+1)\) 的展开级式，即令 \(F=\sum_{i=1}^{\infty}\frac{a_{i}(-1)^{i-1}x^i}{i}\)，对 \(F\) 直接 \(\exp\) 即可。

而非常神奇的事情是将带权 \(\text{burnside}\) 级式写出来后由于圆排列方案数为 \((i-1)!\)，除以 \(i\) 后即为 \(\frac{1}{i}\)，即 \(F=\sum_{i=1}^{\infty}\frac{a_{i}x^i}{i}\)，与互异关系只有 \((-1)^{i-1}\) 的系数差异。

如果将 \(a_{i}\) 写为 \(H(x^i)\) 的形式，那么双方均可规约于 \(\text{eular}\) 变换的变换形式，一般情况下互异关系数的 \(a_{i}< a_{i+1}\)，与带权 \(\text{burnside}\) 的 \(a_{i}\leq a_{i+1}\) 都划归为了 \(\text{eular}\) 变换的形式，变为同一问题。

类似的双者的一些带权复合也是可以的，只需要通过权值函数求出 \(\text{GF}\) 的系数，例如这个题：

所有出现次数为 \(c\) 的产生了 \(\frac{1}{c}\) 的贡献，于是将原权值函数与互异关系容斥函数相复合一下就可以得到 \(\sum_{i=1}^{\infty}\frac{(-1)^{i-1}(\sum_{j=1}^{\infty}\frac{1}{j^kj!}x^j)^{i}}{i}\) 的式子，其实就是对里面那块东西求 \(\text{ln}\) 就可以求出系数。

直接 \(O(n^2)\) $\text{ln,exp} $ 由于巴塞尔问题即可 \(O(n^2)\) 解决，由于最终系数要一边点乘一边算，难以导出 \(\text{GF}\) 封闭形式，于是使用分治 \(\text{FFT}\) 可以 \(O(n \log^3 n)\)。

对于组合对象的 \(<\)，\(\leqslant\) 限制都可以尝试分别用互异关系容斥，带权 \(\text{burnside}\) 解决，注意不要用反，否则可能导致较高复杂度。