一个简单的做法

zhouyuhang · 2024-02-18 18:45:11 · 题解

记 U^V 标准分解为 \prod_{i=1}^k p_i^{\alpha_i}，那我们只需对每个 i 求出答案模 p_i^{\alpha_i} 的值，最后做一遍 CRT 合并就行了。

将每个连通块 S 的权值看作一个多项式 F_S(x)=\prod_{v\in S}(a_v+x)，则答案为 \sum_{i=1}^n\sum_{|S|=i}F_S(i)。接下来我们注意到这样一个结论：对整系数多项式 F(x) 而言，F(x)\equiv F(x)\bmod x^{\underline {pk}}\pmod {p^k}。这就意味着 F(S) 对 p^k 取模后变成了一个至多 pk-1 次的多项式。那么我们直接将 1\sim pk 代入 x 做 O(n^2) dp，最后拉插回来即可。

总复杂度 O(n^2\sum_{i=1}^kp_i\alpha_i)，理论上比标算优秀一些。