瞎写多项式
kevinZ99
·
·
算法·理论
多项式
多项式乘法
C(X)=A(X) \times B(X)
一开始我们可以想到使用拉格朗日插值进行求解。
即带入 x_{0} \cdots x_{n} 求点值，得到 C 在 x_{0} \cdots x_{n} 的点值。
然后使用拉格朗日插值进行求解。
这样仍然是 \mathcal{O}(n^{2})。
但是我们发现拉格朗日插值对 x 并没有要求。
假设答案对 P 取模。
NTT
求点值
我们先令 n 为 A 的长度的，m 为 B 的长度，T 为比 n+m 大的最小的 2 的幂次。
我们尝试带入原根，换句话说。
x_{i}=\omega_{T}^{i}
若 t=\frac{T}{2}。
则我们可以发现 x_{i}+x_{i+t}=P。
:::info[Proof]
\omega_{T}^{T}=(\omega_{T}^{t})^{2}=1
\because \omega_{T}^{t} \ne 1,\mid \omega_{T}^{t} \mid = 1
\therefore \omega_{T}^{t} = -1
\therefore x_{i}+x_{i+t}=\omega_{T}^{i}+\omega_{T}^{i+t}=\omega_{T}^{i}(1+\omega_{T}^{t})=\omega_{T}^{i}(1-1)=0
:::
所以我们可以将 x 分成两半，后一半是前一半每一项的相反数。
于是我们可以在计算点值的时候按照奇偶项拆分。
于是。
对于奇数的项，取相反数。
对于偶数的项，直接复制。
我们将 A(x) 拆成两个多项式 A_{0}(x),A_{1}(x) 分别为奇数项和偶数项。
则。
A_{0}(\omega_{T}^{j})=\sum_{i=0}^{t}a_{2i}\omega_{T}^{2ij}
A_{1}(\omega_{T}^{j})=\omega_{T}^{j}\sum_{i=0}a_{2i+1}\omega_{T}^{2ij}
观察到 \omega 的上下是可以约分的。
:::info[Proof]
\omega_{T}^{2ij}=g^{(\frac{P-1}{T})2ij}=g^{(\frac{p-1}{t})ij}
:::
于是可以得到。
A_{0}(\omega_{T}^{j})=\sum_{i=0}^{t}a_{2i}\omega_{t}^{ij}
A_{1}(\omega_{T}^{j})=\omega_{T}^{j}\sum_{i=0}a_{2i+1}\omega_{t}^{ij}
于是我们考虑分治得到答案复杂度是 T \log{T}
还原多项式
就是在点值的基础上再一次带入点值。
由前面我们可以得到。
v_{i}=\sum_{j=0}^{T-1}a_{j}\omega_{T}^{ij}
我们将 v 看成多项式，带入点值 x_{i}=\omega_{T}^{-i} 即可。
FFT
观察到我们 NTT 需要取的 P \in \mathbb{P} 的要求是 P-1=y2^{x} 其中 x \ge \log{n+m} 而我们使用复数进行求解就没有这一种担忧了，因为可以使用 long double 等高精度的数据类型存储。
多项式乘法逆
给定 A(X) 求 B(X) 满足 A(XBG(X) \equiv 1\pmod{x^{n}}。
考虑倍增。
已知 A*B'\equiv 1\pmod{x^{\frac{n}{2}}}。
B-B'\equiv 1\pmod{x^{\frac{n}{2}}}
平方再乘以 A(X) 可以得到。
B \equiv 2B'-AB'^{2} \pmod{x^{n}}
任意模数多项式乘法逆
采用 3 mod NTT 就是使用 3 个 NTT 友好模数，然后使用 crt 合并。
任意模数多项式乘法
同样可以使用 3 mod NTT 解决。
多项式除法
P4512
特别厉害。
定义一个 reverse 操作 A_{R}(x)=x^{n}A(\frac{1}{x})
F(x)=Q(x)*G(x)+R(x)
F(\frac{1}{x})=Q(\frac{1}{x})*G(\frac{1}{x})+R(\frac{1}{x})
F_{R}(x)=Q_{R}(x)*G_{R}(x)+x^{n-m+1}*R_{R}(x)
于是。
F_{R}(x)\equiv Q_{R}(x)*G_{R}(x)\pmod{x^{n-m+1}}
Q_{R}(x)\equiv F_{R}(x)*G_{R}^{-1}(x)\pmod{x^{n-m+1}}
多项式开根
照样倍增。
容易得到。
G(X)=\frac{F(X)+H^{2}(X)}{2H(X)}
其中 H(X) 是前一次的答案。
其实到这里可以发现，我们多项式是一个操作依赖前一个操作的，所以常数越堆越大。
例题
P4002
观察到 m=1 的时候 \sum d 是固定的，于是我们发现可以直接一个点一个点的 dp 即可。
观察到 m=2 的时候将 \sum d 是可以拆开乘到 \prod 里面，那么相当于在 \text{Prufer} 序列里面的一种数字里面打上两个标记的方案数，可以不选。
于是我们可以 f_{i,j} 表示到了第 i 个位置打了 j 个标记。
同理可以扩展到 m 个，然后使用多项式乘法优化到 nm\log^{2}{n} 了。
P5395
观察斯特林数时的组合意义，题目中已经给出了，我们观察到需要每一个盒子必然要有球，于是我们考虑容斥。
\begin{Bmatrix} n \\m \end{Bmatrix}=\sum_{i=0}^{m}\frac{i^{n}(-1)^{m-i}}{i!(m-i)!}
于是直接多项式就可以过了。
P5396
可以用生成式函数来做。
假设 f_{n}(x)=\sum_{i \ge 0}\begin{Bmatrix} n \\m \end{Bmatrix}x^{i}。
于是。
f_{m}(x)=xf_{m-1}(x)+mxf_{m}(x)
f_{m}(x)=\frac{x^{m}}{\prod_{i=1}^{m}(1-ix)}
于是我们使用分治求出下面，然后求逆后偏移 m 位即可。
P5408
容易观察到可以使用生成式函数，然后同上推理，我们可以得到。
就是 \prod_{i=0}^{n-1}(x+i) 然后我们使用分治求出。