Similar Polynomials

· · 题解

题目链接

CF1817C Similar Polynomials

题解

这里给出一个比较寻的做法。

我们考虑已知 d 次多项式的 d + 1 个点值，我们就可以将这个多项式插值出来，但是直接做是 \Theta(d \log ^ 2 d)，所以无法通过。

然后考虑多项式 A 和 B 之间的关系，设：

A = \sum_{i = 0} ^ d a_i x ^ i, B = \sum_{i = 0} ^ d b_i x ^ i

显然有：

B = \sum_{i = 0} ^ d b_i x ^ i = \sum_{i = 0} ^ d a_i (x + s) ^ i

然后推一下式子：

\sum_{i = 0} ^ d a_i (x + s) ^ i = \sum_{i = 0} ^ d a_i \times \sum_{j = 0} ^ i \binom{i}{j} x ^ j \cdot s ^ {i - j} = \sum_{j = 0} ^ d \sum_{i = j} ^ d \binom{i}{j} a_i \cdot s ^ {i - j} x ^ j

然后我们就有：

b_i = \sum_{j = i} ^ d \binom{j}{i} a_j \cdot s ^ {j - i}

考虑一个特殊情况，当 i 取到 d - 1 时：

b_{d - 1} = a_{d - 1} \times s + a_d \times d s = \dfrac{b_{d - 1} - a_d \times d}{a_{d - 1}}

所以我们并不需要知道多项式 A 和 B 的所有系数，只需要知道 x ^ {d - 1} 项和 x^d 项的系数。

然后考虑拉格朗日插值，假如已知多项式 F 经过 d + 1 个点 (x_0, y_0), (x_1, y_1), \cdots, (x_d, y_d)：

F(x) = \sum_{i = 0} ^ d y_i \times \prod_{j \neq i} \dfrac{x - x_j}{x_i - x_j}

所以多项式 F 就是这个式子，然后考虑变形一下：

F(x) = \sum_{i = 0} ^ d \dfrac{y_i}{\prod\limits_{j \neq i} (x_i - x_j)} \times \prod_{j \neq i} (x - x_j)

然后求 x ^ d 项系数就是：

[x ^ d] F(x) = \sum_{i = 0} ^ d \dfrac{y_i}{\prod\limits_{j \neq i} (x_i - x_j)}

可以理解成对于每个 i，前面的系数是固定的，然后考虑后面 \prod\limits_{j \neq i} (x - x_j)，只有在每一项都取 x 时才能够达到 x ^ d，所以这部分的贡献就是 1，然后就加起来就行了。

求 x ^ {d - 1} 项系数也类似：

[x ^ {d - 1}] F(x) = \sum_{i = 0} ^ d \dfrac{y_i}{\prod\limits_{j \neq i} (x_i - x_j)} \times \sum\limits_{j \neq i} (-x_j)

跟上面类似，前面系数固定，后面如果要取到 x ^ {d - 1} 就必须恰好有一处是取到形如 -x_k，其余全部取到 x，所以贡献就是 \sum\limits_{j \neq i} (-x_j)，然后相乘后相加就行了。

至此，只需要预处理出阶乘逆元即可，时间复杂度 \Theta(d)。

代码链接

https://codeforces.com/contest/1817/submission/203954733