ZJOI2018 树

发布时间 2023-12-05 19:10:33作者: zhouhuanyi

互异关系容斥即将不等号容斥成等号,对于连通块内的 \(\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}\) 解决,注意不要用反,否则可能导致较高复杂度。