多项式的一些奇怪操作

之前讲了一些多项式常用的操作

多项式除法与取模

对于一个 $n$ 次多项式 $A(x)$ 和一个 $m$次多项式 $B(x)$. $m\leq n$ .
求 $Q(x),R(x)$ 使
$$ A(x)\equiv Q(x)* B(x)+R(x) $$
其中 $Q(x)$ 是一个 $n-m$ 次多项式,而 $R(x)$ 是一个小于 $m$ 次的多项式
可以在 $O(n\log n)$ 复杂度内求出,求解思路清奇,一般记结论就行了。
记 $A^{r(n)}(x)$ 表示一个次数小于等于 $n$ 的多项式 $A(x)$ 以 $x^n$ 为最高次项进行翻转得到的多项式
显然 $A^{r(n)}(x)=x^n*A(\frac{1}{x})$

$$ A^{r(n)}(x)=x^nQ(\frac{1}{x})B(\frac{1}{x})+x^nR(\frac{1}{n}) $$
$$ A^{r(n)}(x)=x^{n-m}Q(\frac{1}{n})x^mB(\frac{1}{x})+x^nR(\frac{1}{n}) $$
$$ A^{r(n)}(x)=Q^{r(n-m)}(x)B^{r(m)}(x)+R^{r(n)}(x) $$
注意到 $R^{r(n)}(x)$ 的前 $n-m$ 项都是 $0$ ,而我们要求的 $Q(x)$ 则只有前 $n-m$ 项可能不为 $0$
$$ A^{r(n)}(x)\equiv B^{r(m)}(x)Q^{r(n-m)}(x) \pmod{x^{n-m+1}} $$
$$ Q(x) \equiv (\cfrac{A^{r(n)}(x)}{B^{r(m)}(x)})^{r(n-m)} $$
然后可以用多项式求逆算出。
求出商之后取模并不困难。

多项式多点操作问题

由于这类问题比较鬼畜不好区分,所以一般是不会考的(拉格朗日插值还是有可能)

多点求值

给 $n$ 个数 $x_1,x_2\dots x_n$ 和一个 $m$ 次多项式 $f(x)$ ,求 $f(x_1),f(x_2)\dots f(x_n)$
简单暴力O(nm)
首先分割数字集 $X_1={x_1,x_2\dots x_{\lfloor\frac{n}{2}\rfloor}}, X_2={x_{\lfloor\frac{n}{2}\rfloor +1}\dots x_n}$
设 $P_1(x)=\prod_{i=1}^{\lfloor\frac{n}{2}\rfloor}(x-x_i), P_2(x) = \prod_{i=\lfloor\frac{n}{2}\rfloor +1}^{n} (x-x_i) $
$$f(x)=P_1(x)\cdot D(x)+R(x) $$
对于 $X_1$ 中数字求值时, $f(x_i)=P_1(x_i)\cdot D(x_i)+R(x_i) $
而 $P_1(x_i)=0$ ,故 $f(x_i)=R(x_i)$
通过多项式除法和取模可以得到一个次数为 $n-\lfloor\frac{n}{2}\rfloor$ 的 $R(x)$ 。
需要注意的是求 $P(x)$ 也需要使用分治 代码长度感人

多点插值

给出 $n$ 对二元组 $(x_i, y_i)$ ,求一个函数 $f(x).\forall (x_i, y_i), f(x_i)=y_i$

拉格朗日插值

基础做法,使用比较普遍,但是复杂度 $O(n^2)$ 不够优秀,这里也给出方法
$$ f(x)=\sum_{i=1}^{n}\cfrac{\prod_{i\neq j} (x-x_j)}{\prod_{i\neq j}(x_i-x_j)} \cdot y_i $$

分治做法

个人感觉这个做法比较鬼畜。。。
首先把 $x_i$ 分成两组。
看上去可以像多点求值一样分治做了好开心,但是显然两组之间是互相影响的,我们要保证得出的式子同时满足两组式子。
先假设递归插值出了前一组,得到多项式 $A(x)$
此时任然考虑多项式 $P(x)=\prod(x-x_i)$
可以把最终插值出的多项式写成 $ F(x)=B(x)\cdot P(x)+A(x) $
$ B(x) $ 是一个不确定的多项式,将 $F(x)$ 写成这样可以保证无论 $B(x)$ 是怎样的多项式, $A(x)$ 对于第一组的二元组都是满足条件的,此时考虑第二组。
要使得第二组的 $x_i$ 满足 $y_i=B(x_i)*P(x_i)+A(x_i) $
也就是说 $B(x_i)=\cfrac{y_i-A(x_i)}{P(x_i)}$
然后对于新的 $B(x_i)$ 插值求出 $B(x)$ 然后就可以得到 $F(x)$ 了
复杂度 $T(n)=2\times T(\frac{n}{2})+O(n\log ^2 n)=O(n\log ^3 n)$

其他可能有用的知识

$n^m$ 的拆分

$n^m$ 的组合意义是将 $m$ 个不同元素分成 $n$ 个不同集合,集合可以为空,而第二类斯特林数 $S(m,n)$ 表示将 $m$ 的元素放入 $n$ 个相同集合,集合不可以为空的方案
所以可以考虑枚举这 $n$ 个集合中有几个集合是非空的,然后由于斯特林数划分是相同的集合,所以在最后乘上一个 $i!$
$$ n^m=\sum_{i=0}^{n}S(m,i)C_{n}^{i}\times i! $$
对于斯特林数的求法
$$ S(n,m)=\frac{1}{m!} \sum_{i=0}^{m}(-1)^i C_m^i (m-i)^n $$
上面是一个可以卷积的式子,这个东西经常出现在省选中,要注意一下

任意模数的卷积

  • 拆分法,将数字拆成 $kM+b$ 的形式,具体方法就不说了
  • 中国剩余定理,找三个很大的模数 $M_1,M_2,M_3$ 保证 $M_1\cdot M_2\cdot M_3>MOD^2\cdot n$ ,这个做法要写高精度,比较恶心

拉格朗日反演

奇怪的定理
若对于函数 $f(x),g(x)\in F[[x]]$ ( $F$ 下形式幂级数环) $f(g(x))=x$
$$ [x^n]g(x)=\frac{1}{n}[x^{n-1}]\big{(} \frac{x}{f(x)}\big{)} ^n $$
扩展:定义 $F^{-1}(x)$ 为 $F(x)$ 的复合逆,那么
$$ [x^n]G(F^{-1}(x))=\frac{1}{n}[x^{-1}]\big{(}\frac{dG(x)}{dx}\frac{1}{F^n(x)}\big{)} $$
这个当结论记都有点困难了,当然也不太会用。

引用资料

lc 讲课资料

sys_con

OIer,常规 / 竞赛都渣得不行