题解 P5245 【【模板】多项式快速幂】

Light_Poet · 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)