自动搬运

查看原文

来自洛谷，原作者为

	Light_Poet 这个人很菜，什么也没法留下

搬运于2025-08-24 22:08:38，当前版本为作者最后更新于2021-01-12 20:32:11，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

我们可以直接做多项式 $\ln$ 并乘以 $k$ 然后进行多项式 $\exp$

为此会导出一个问题：我们将 $k$ 对 $p$（模数）进行了取模，似乎无论 $k$ 多大这都是正确的。

以下内容节选自 EI 鸽鸽的集训队论文：

下面说明一个更一般的情况：

设 $f(x)$ 为一个 $n$ 次多项式，$p$ 为质数。

当我们计算 $f(x)^p\bmod x^n$ 时，由于一般情况下 $n<p$，所以 $f(x)^p\equiv a_0=1(\text{本题})$，故我们可以直接将 $k$ 对 $p$ 取模。

证明的话可以考虑到 $(a+b)^p\equiv a^p+b^p\pmod p$

使用归纳证明：

设 $f(x)$ 为 $k$ 阶多项式，$a_k$ 为其第 $k$ 项系数，设 $f(x)=g(x)+a_kx^k$，且上述结论对于 $k-1$ 阶多项式成立。

考虑到：$f(x)^p=g(x)^p+a_k^px^{pk}=g(x^p)+a_kx^{pk}=f(x^p)$