自动搬运

查看原文

来自洛谷，原作者为

	zhouyuhang Bénédiction de Dieu dans la solitude

搬运于2025-08-24 22:55:25，当前版本为作者最后更新于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)$，理论上比标算优秀一些。