P1916 题解

· · 题解

容易发现若令 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) 的空间复杂度内解决了此问题。