自动搬运

查看原文

来自洛谷，原作者为

	zjy2008 else if

搬运于2025-08-24 21:31:51，当前版本为作者最后更新于2025-05-02 12:53:36，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

容易发现若令 $F(x)=\sum g_{j,i}(x-a_j)^i$ 则 $F^{(j)}(a_i)=j!g_{i,j}$。于是问题变成了求出 $F(x+a_i)\bmod x^{k_i}$ 的系数，我们可以把它分解成 $F(x)\bmod (x-a_i)^{k_i}$ 和已知 $G(x)$，求出 $G(x+a_i)$ $2$ 步。

先考虑第 $2$ 步，直接写出系数表达：

$$G(x+a)=\sum g_i(x+a)^i=\sum g_i\binom{i}{j}a^{i-j}x^j=\sum (i!g_i)\dfrac{a^{i-j}}{(i-j)!}\dfrac{x^j}{j!} $$

直接一次差卷积即可解决。

考虑第 $1$ 步，容易得到基于多项式取模的 $O(n\log n\log m)$ 做法。类似多项式多点求值地，将 $Q_i=(x-a_i)^{k_i}$ 放在线段树上，自上而下地做多项式取模。

接下来的常数优化也是众所周知的：利用转置原理。介绍一种容易理解的方法（来自 飞雨烟雁 的博客）。

考虑简化多项式取模的操作。

记下标 $r$ 为系数翻转，$n,m$ 分别为 $F,G$ 的最高次数。

我们有 $[x^k](F\bmod G)=\sum [x^i]F[x^k](x^i\bmod G)$。对其转置，得到 $[x^k](F\bmod^T G)=\sum [x^i]F[x^i](x^k\bmod G)$

可以发现这是在求解一个初值为 $[x^0]F,[x^1]F,\cdots$，递推系数为 $G$ 的线性递推。而我们知道线性递推可以被另一种方式表达：$\dfrac{(FG_r)\bmod x^m}{G_r}$，所以它也是取模的转置，那么我们可以再转置回来得到多项式取模，得到：

$$F\bmod G=((F\times^T G_r^{-1})\bmod x^m)\times^T G_r $$

于是一切豁然明朗，直接在线段树上维护出子树内的 $\prod G_r$，向下传 $(F\times^T G_r^{-1})\bmod x^m$ 即可。

于是我们在 $O(n\log n\log m)$ 的时间复杂度，$O(n\log m)$ 的空间复杂度内解决了此问题。