wiki - 算法小站

主题名称

是否为父主题

是否为其添加wiki文章

选择主题

修改主题名称

修改父主题

修改wiki文章

算法基础搜索数据结构字符串数学图论动态规划计算几何杂项

数学

组合计数

二项式定理

生成函数（一）

FFT

多项式与形式幂级数

[[ item.c ]]

多项式与形式幂级数

## 多项式的运算
多项式的常见运算，包括多项式的积分，多项式的逆元（模$$x^m$$意义下）
多项式的指数函数（求多项式的exp），多项式的幂函数
### 多项式的基础运算
**modxk**
求多项式$$A(x) \mod x^k$$，实际上只保留多项式$$x^0 \sim x^{k-1}$$这些项
如果将$$A(x) = \sum_i a_ix^i$$，并且用系数`a[0...n-1]`来表示最高$$n-1$$阶的多项式
```bash
Poly modxk(int k) const {
	k = std::min(k, size());
	return Poly(std::vector<cd>(a.begin(), a.begin()+k));
}
```
**mulxk**
求$$A(x) \cdot x^k$$，关于$$x$$的幂指，$$x^{[0\cdots n-1]} \cdot x^k$$
那么$$x$$的新的幂指范围是$$[k, k+n-1]$$，此时需要补上幂指为$$[0, k-1]$$的这些项
这些项的系数都是`0`
```bash
Poly mulxk(int k) const {
	auto b = a;
	b.insert(b.begin(), k, cd(0, 0));
	return Poly(b);
}
```
**divxk**
求$$A(x) / x^k$$
同样考虑幂指范围，$$A(x) \in [0\cdots n-1], A(x)/x^k \in [-k\cdots n-1-k]$$
那么**原来幂指范围在**$$[0\cdots k-1]$$的项均消失了，对应的系数也不存在了
对于$$A(x) / x^k$$，有效的系数是从$$a[k\cdots]$$开始的
```bash
Poly divxk(int k) const {
	if (size() <= k) return Poly();
	return Poly(std::vector<cd>(a.begin()+k, a.end()));
}
```
### 多项式的求导和积分
**deriv**
实际上是求$$A(x)^{\prime}$$
```math
A(x) = a_0 + a_1x^1 + a_2x^2 + \cdots a_ix^i + \cdots a_{n-1}x^{n-1} \\
A(x)^{\prime} = a_1 + 2a_2x + \cdots + ia_ix^{i-1} + (i+1)a_{i+1}x^i + \cdots
```
不难发现$$res(i) = (i+1)a\_{i+1}$$
```bash
Poly deriv() const {
	if (a.empty()) return Poly();
	std::vector<cd> res(size() - 1);
	for (int i = 0; i + 1 < size(); i++) res[i] = cd(i+1, 0) * a[i+1];
	return Poly(res);
}
```
**integr**
```math
\int A(x) = a_0x + \dfrac{1}{2}a_1x^2 + \cdots + \dfrac{1}{i+1} a_i x^{i+1} + \cdots 
```
由此$$res(i+1) = \dfrac{a_i}{i+1}$$
```bash
Poly integr() const {
	std::vector<cd> res(size() + 1);
	for (int i = 0; i < size(); i++) res[i+1] = a[i] / cd(i+1, 0);
	return Poly(res);
}
```
## 求多项式的逆元
给定一个多项式$$A(x)$$，其次数为$$deg_A$$，若存在一个多项式$$B(x)$$
使其满足$$deg_B \leqslant deg_A$$，并且$$A(x)B(x) \equiv 1(\bmod x^n)$$
那么称$$B(x)$$是$$A(x)$$在模$$x^n$$意义下的乘法逆元

不妨假设$$n = 2^k, k \in N$$
若$$n = 1$$，则$$A(x)B(x) \equiv a_0 \times b_0 \equiv 1 (\bmod x^1)$$
其中$$a_0, b_0$$都是常数项，直接用费马小定理求逆元

若$$n > 1$$，用**牛顿迭代**，假设在$$\bmod x^{\frac{n}{2}}$$下，$$A(x)$$的逆元$$B_0(x)$$已经求出来了
```math
\displaystyle
A(x)B_0(x) \equiv 1 (\bmod x^{\frac{n}{2}}) \\
A(x)B_0(x) - 1 \equiv 0 (\bmod x^{\frac{n}{2}})
```
两边平方
```math
\displaystyle
A^2(x)B_0^2(x) - 2A(x)B_0(x) + 1 \equiv 0 (\bmod x^n) \\
\quad \\
\begin{cases}
2A(x)B_0(x) - A^2(x)B_0^2(x) \equiv 1(\bmod x^n) \\
A(x)B(x) \equiv 1 (\bmod x^n)
\end{cases} \\
\quad \\
A(x)B(x) \equiv 2A(x)B_0(x) - A^2(x)B_0^2(x) (\bmod x^n) \\
B(x) \equiv B_0(x) (2 - A(x)B_0(x)) (\bmod x^n)
```

初始化$$x = \dfrac{1}{a_0}$$，迭代
```bash
取 mod x^m
int k = 1
while k < m:
	then k <<= 1;
	x <-- x * (2 - (this.modxk(k)) * x).modxk(k)
	// x 就是迭代的 B0(x), this.modxk(k) = A(x) mod x^k
```
多项式求逆
```bash
Poly inv(int m) const {
	// assume a[0] != 0
	Poly x{ cd(1.0, 0) / a[0] };
	int k = 1;
	while (k < m) {
		k <<= 1;
		x = (x * ( Poly(cd{2, 0}) - modxk(k) * x )).modxk(k);
	}
	return x.modxk(m);
}
```
## 形式幂级数的对数
**log(int m)**，截断到$$x^{m-1}$$，即$$\bmod x^m$$
对于常数项为`1`的幂级数$$A(x)$$，要求$$a_0 = 1$$
```math
\displaystyle
\ln A(x) = \int \dfrac{A'(x)}{A(x)} dx
```
```bash
Poly log(int m) const {
	return (deriv() * inv(m)).integr().modxk(m);
}
```
## 多项式指数函数
### 牛顿迭代
如果一个方程形如
```math
\displaystyle
F(G(x)) \equiv 0 (\bmod x^n)
```
而已经知道$$F(G_0(x)) \equiv 0 (\bmod x^{\lceil \frac{n}{2} \rceil})$$
那么可以用牛顿迭代来求解

> 考虑将$$F(G(x))$$在$$G_0(x)$$处 Taylor 展开

```math
\displaystyle
F(G(x)) = \sum_{n = 0}^{\infty}\dfrac{F^{(n)} (G_0(x))}{n!} (G(x) - G_0(x))^n \equiv 0 (\bmod x^n)
```
又因为我们有（以下式子两边平方）
```math
\displaystyle
G(x) - G_0(x) \equiv 0 (\bmod x^{n/2}) \\
\Rightarrow (G(x) - G_0(x))^2 \equiv 0 (\bmod x^n)
```
那么 Taylor 展开的$$(\bmod x^n)$$表达式中，从$$()^2, ()^3, \cdots$$以后都是`0`
```math
\displaystyle
F(G(x)) = F(G_0(x)) + F'(G_0(x))(G(x) - G_0(x)) \equiv 0 (\bmod x^n)
```
两边同时$$/ F'(G_0(x))$$，再移项
```math
\displaystyle
G(x) \equiv G_0(x) - \dfrac{F(G_0(x))}{F'(G_0(x))} (\bmod x^n)
```
### 求多项式指数函数
实际上给定$$A(x)$$，求$$G(x) \equiv e^{A(x)} (\bmod x^n)$$，即我们要求
```math
\displaystyle
\ln G(x) - A(x) \equiv 0 (\bmod x^n)
```
迭代的函数方程是
```math
\displaystyle
F(G) = \ln(G) - A
```
**边界情况**，$$n = 1$$必须有$$a_0 = 0, g_0 = e^{a_0} = 1$$
方程$$\ln g_0 - a_0 = 0 \equiv 0 (\bmod x^1)$$成立

所求的$$G(x)$$的常数项$$g_0 = 1$$即可

然后开始迭代
```math
\displaystyle
F'(G) = \dfrac{1}{G} = \dfrac{1}{G(x)} \\
\quad \\
G(x) \equiv G_0(x) - \dfrac{\ln G_0(x) - A(x)}{\dfrac{1}{G_0(x)}} (\bmod x^n) \\
\quad \\
G(x) \equiv G_0(x)(1 - \ln G_0(x) + A(x)) (\bmod x^n)
```
下面**迭代**的时候，令$$x \leftarrow G_0(x)$$
```bash
Poly exp(int m) const {
	Poly x{cd(1, 0)};

int k = 1;
	while (k < m) {
		k <<= 1;
		x = (x * ( Poly{cd(1, 0)} - x.log(k) + modxk(k) )).modxk(k);
	}
	return x.modxk(m);
}
```
## 多项式幂函数
给定一个$$n - 1$$次多项式$$A(x)$$，求一个在$$\bmod x^n$$意义下的多项式$$B(x)$$
使得$$B(x) \equiv (A(x))^k (\bmod x^n)$$
```math
\displaystyle
B(x) \equiv (A(x))^k (\bmod x^n) \\
\ln B(x) \equiv k \ln A(x) (\bmod x^n)
```
要求多项式$$\ln A(x)$$，必须要$$a_0 = 1$$，那很多时候如果$$a_0 = 0$$怎么办？
可以找到$$i$$是第一个**非`0`的项**，即$$a_i \neq 0$$
那么这时候多项式的幂至少应该是$$(x^i)^k$$，如果$$ik \geqslant m$$
答案就是$$[0\cdots m-1]$$均为`0`的多项式

否则，可以令
```math
\displaystyle
A(x) = vx^i + \cdots \\
\quad \\
\dfrac{A(x)}{x^i} = v + a_{i+1}x + \cdots 
```
记$$f(x) = \dfrac{A(x)}{vx^i}$$，恰好满足$$f_0 = 1$$，常数项是`1`

可以用相关的$$\ln, \exp$$

```math
\displaystyle
A(x) = v \cdot x^i \cdot f(x) \\
A^k(x) = x^{ik} \cdot f^k(x) \cdot v^k
```
> 先考虑求$$f^k(x)$$

```math
\displaystyle
f^k(x) = \exp(k \cdot \ln f(x))
```
注意到我们要求的是$$A^k(x) \bmod (x^m)$$
而$$A^k(x) = O(x^{ik} \cdot f^k(x))$$
所以对应的，实际上我们应该求$$f^k(x) \bmod (x^{m - ik})$$
这里求出的答案应该是（下面用**伪代码**描述）
```math
f^{k}(x) = \left( (f.\log(m-ik)) \cdot k \right).\exp(m-ik) \\
A^k(x) = f^{k}(x).mulxk(ik) \cdot v^k
```
整体的算法流程如下
```bash
Poly pow(int K, int m) const {
	int i = 0;
	while (i < size() and is_zero(a[i])) i++;

if (i == size() or 1LL * i * K >= m) return Poly(std::vector<cd>(m));

cd v = a[i];
	Poly f = divxk(i) * (cd(1, 0) / v);
	return (f.log(m - i*K) * double(K)).exp(m - i*K).mulxk(i * K) * power(v, K);
}
```

## 多项式开根
给定一个$$n-1$$次多项式$$A(x)$$，求一个$$\bmod x^n$$意义下的多项式$$B(x)$$
使得$$B^2(x) \equiv A(x) (\bmod x^n)$$
```math
\displaystyle
B^2(x) \equiv A(x) (\bmod x^m) \\
\quad \\
F(B) = B^2 - A, \quad F'(B) = 2B
```
用**牛顿迭代**
```math
\displaystyle
B(x) \equiv B_0(x) - \dfrac{B_0^2(x) - A(x)}{2B_0(x)} \\
\equiv \dfrac{B_0^2(x) + A(x)}{2B_0(x)}
```
实际上迭代的时候，我们有
```math
\displaystyle
x_{new} = \dfrac{1}{2}\left( x + \dfrac{A}{x} \right)(\bmod x^k)
```
```bash
Poly sqrt(int m) const {
	Poly x{cd(1, 0)};
	int k = 1;
	while (k < m) {
		k <<= 1;
		x = (x + (modxk(k) * x.inv(k)).modxk(k)) * cd(0.5, 0);
	}
	return x.modxk(m);
}
```

## 转置原理和多项式多点求值
### 转置原理
如果$$\bm{C} = \bm{AB}$$，那么$$\bm{C}^T = \bm{B}^T \bm{A}^T$$
已知矩阵$$\bm{A}$$，输入向量$$\bm{f}$$，那么称$$\bm{g = Af}$$和$$\bm{g}^T = \bm{A}^T\bm{f}$$互为转置

若矩阵$$\bm{A}$$可逆，并且$$\bm{A}$$可以分成若干**初等矩阵**$$\bm{A} = \bm{A}\_n \cdots \bm{A}\_2\bm{A}\_1$$相乘（看作线性变换的复合）

如果发现$$\bm{g = Af}$$较难求出来
可以考虑求解$$\bm{g}^T = \bm{A}\_1^T \bm{A}\_2^T \cdots \bm{A}\_n^T \bm{f}$$

把**线性变换的路径**，即每一个$$\bm{A}\_i^T$$记录下来
然后按照相反的顺序，即可以求出$$\bm{g}$$
```math
\displaystyle
\bm{f} \xrightarrow{\bm{A}_1} ? \xrightarrow{\bm{A}_2} \cdots \xrightarrow{\bm{A}_n} \bm{g} \\
\quad \\
\bm{f} \xrightarrow{\bm{A}_n^T} ? \xrightarrow{\bm{A}_{n-1}^{T}} \cdots \xrightarrow{\bm{A}_1^T} \bm{g}^T
```

### 转置卷积
考虑普通的卷积，$$\bm{C} = \bm{BA}$$，我们有$$\displaystyle c\_k = \sum\_{i+j = k}a\_i b\_j$$

```math
\displaystyle
\begin{pmatrix}
b_0 & 0 & 0 & \cdots & 0 \\
b_1 & b_0 & 0 & \cdots & 0 \\
b_2 & b_1 & b_0 & \cdots & 0 \\
\vdots & \vdots & \vdots & \cdots & \vdots \\
b_{n-1} & b_{n-2} & b_{n-3} & \cdots & b_0 \\
\end{pmatrix}
\begin{pmatrix}
a_0 \\
a_1 \\
a_2 \\
\vdots \\
a_{n-1}
\end{pmatrix} = \\
\begin{pmatrix}
b_0a_0 \\
b_1a_0 + b_0a_1 \\
b_2a_0 + b_1a_1 + b_0a_2 \\
\vdots \\
b_{n-1}a_0 + b_{n-2}a_1 + \cdots + b_0a_{n-1}
\end{pmatrix}
```

考虑将$$\bm{B}$$转置成$$\bm{B}^T$$
```math
\displaystyle
\begin{pmatrix}
b_0 & b_1 & b_2 & \cdots & b_{n-1} \\
0 & b_0 & b_1 & \cdots & b_{n-2} \\
0 & 0 & b_0 & \cdots & b_{n-3} \\
\vdots & \vdots \\
0 & 0 & 0 & \cdots & b_0
\end{pmatrix}
\begin{pmatrix}
a_0 \\
a_1 \\
a_2 \\
\vdots \\
a_{n-1}
\end{pmatrix} = \\
\quad \\
\begin{pmatrix}
b_0a_0 + b_1a_1 + b_2a_2 \cdots + b_{n-1}a_{n-1} \\
b_0a_1 + b_1a_2 + \cdots \\
b_0a_2 + b_1a_3 + \cdots
\end{pmatrix}
```
不难发现，满足
```math
\displaystyle
c_k = \sum_{i-j=k}a_ib_j, \quad \bm{C}(x) = \sum_{k}a_{i+k}b_k \cdot x^i
```
也可以记为
```math
\displaystyle
c_i = \sum_{k} a_{i+k}b_k
```
也就是说，$$\bm{B}^T \bm{A}$$转置卷积，是**减法卷积**
而通常意义下的多项式乘法，做的都是**加法卷积**

> 减法卷积怎么转化成加法卷积，便于我们求解呢？

```math
\displaystyle
c_k = \sum_{i-j = k}a_ib_j
```
**根据卷积的定义**，回到多项式乘法本身，观察**幂指**的关系
```math
\displaystyle
\bm{C}(x) = \sum_{i-j = k} a_ix^i \cdot b_j x^{-j} \\
\quad \\
\bm{C}(x) = \bm{A}(x) \bm{B}(\dfrac{1}{x})
```
如果我们构造
```math
\displaystyle
\bm{B}^T(x) = \sum_{j = 0}^{n-1}b_{n-1-j}x^j \\
\quad \\
= x^{n-1} \sum_{j=0}^{n-1} b_{n-1-j}x^j \cdot x^{-(n-1)} = x^{n-1} \sum_{j = 0}^{n-1}b_{n-1-j}x^{j-n+1} \\
\quad \\
= x^{n-1}\bm{B}(\dfrac{1}{x})
```
也就是有关系$$\bm{B}^T(x) = x^{n-1} \bm{B}(\dfrac{1}{x})$$

综上所述
```math
\displaystyle
\bm{B}^T(x) = b_{n-1} + b_{n-2}x + \cdots + b_0x^{n-1} \\
\quad \\
\bm{C}(x) = \bm{A}(x)\bm{B}^T(x) / x^{n-1}
```
算法就比较简单了
1)先将$$\bm{B}$$的系数翻转，然后做正常的 FFT/NTT 多项式卷积
2)算出结果后，再$$/x^{n-1}$$，即`divxk(n-1)`

```bash
Poly mulT(Poly b) const {
	if (b.size() == 0) return Poly();
	int n = b.size();
	std::reverse(b.a.begin(), b.a.end());
	return ((*this) * b).divxk(n - 1);
}
```
### 多项式的多点求值
给定一个$$n$$次多项式$$\bm{A}(x)$$，对于$$i \in [0, m)$$，求$$\bm{A}(x_i)$$
方便处理，我们将长度扩充到$$n = \max(n+1, m)$$，不够的项补`0`
```math
\displaystyle
A(x_0) = a_0 + a_1x_0 + \cdots + a_{n-1}x_0^{n-1} \\
A(x_1) = a_0 + a_1x_1 + \cdots + a_{n-1}x_1^{n-1} \\
\cdots
```
令$$\bm{X}$$为**范德蒙矩阵**，多点求值实际上是求$$\bm{g} = \bm{Xa}$$
```math
\displaystyle
\begin{pmatrix}
1 & x_0 & x_0^2 & \cdots & x_0^{n-1} \\
1 & x_1 & x_1^2 & \cdots & x_1^{n-1} \\
\vdots & \vdots \\
1 & x_{n-1} & x_{n-1}^2 & \cdots & x_{n-1}^{n-1}
\end{pmatrix}
\begin{pmatrix}
a_0 \\
a_1 \\
\vdots \\
a_{n-1}
\end{pmatrix}
```
现在考虑这个东西很难求，我们尝试去求解$$\bm{g} = \bm{X}^{T}\bm{a}$$
并且**观察线性变换的路径**，最后分治的时候，把**路径反过来**即可
```math
\displaystyle
\begin{pmatrix}
1 & 1 & \cdots & 1 \\
\vdots & \vdots & \cdots & \vdots \\
x_0^k & x_1^k & \cdots & x_{n-1}^k \\
\cdots & \cdots
\end{pmatrix}
\begin{pmatrix}
a_0 \\
\vdots \\
a_k \\
\vdots
\end{pmatrix}
= \begin{pmatrix}
\vdots \\
g_k \\
\vdots
\end{pmatrix}
```
就看第$$k$$行，有
```math
\displaystyle
g_k = \sum_{i = 0}^{n-1}x_i^k a_i
```
考虑其**生成函数**
```math
\displaystyle
G(x) = \sum_{k = 0}^{\infty}g_kx^k = \sum_{k= 0}^{\infty} \left( \sum_{i=0}^{n-1}x_i^k a_i \right) x^k \\
\quad \\
= \sum_{i = 0}^{n-1}a_i \left( \sum_{k = 0}^{\infty} (x_ix)^k \right) \\
\quad \\
= \sum_{i = 0}^{n-1} \dfrac{a_i}{1-x_ix} \\
\quad \\
g_k = [x^k] \sum_{i = 0}^{n-1} \dfrac{a_i}{1 - x_ix}
```

> 但实际上，我们要求的并不是$$\bm{g}$$，而是$$\bm{g}^T$$
没关系，先看看$$\bm{g}$$在分治过程中是怎么变换的

注意到，$$a_i, x_i$$实际上是已知的，分治计算
```math
\displaystyle
\sum_{i = 0}^{n-1} \dfrac{a_i}{1 - x_ix}
```
**叶子结点**，$$P_i = a_i, Q_i = 1 - x_ix$$
**考虑合并**
```math
\displaystyle
\dfrac{P_L}{Q_L} + \dfrac{P_R}{Q_R} = \dfrac{P_LQ_R + P_RQ_L}{Q_LQ_R}
```
其中，分母的合并是简单的，并且是多项式的乘法
（因为所有的$$x_i$$都是已知的），可以**预处理出来**

**考虑分子**
分子是一个线性变换
```math
\displaystyle
\bm{Q} = (Q_R, Q_L), 
\bm{P} = 
\begin{pmatrix}
P_L \\
P_R
\end{pmatrix}
```
从而有
```math
\displaystyle
\bm{P}_{new} = \bm{QP} = (Q_R, Q_L)
\begin{pmatrix}
P_L \\
P_R
\end{pmatrix}
```
1) 先预处理分子$$\bm{Q}$$
2) 在根节点的时候，此时分子$$\bm{P}[1] = \bm{E}\_1\bm{E}\_2 \cdots \bm{E}\_{n}$$
将分子$$\bm{P}[1] \cdot \dfrac{1}{\bm{Q}[0, n)}$$就是最终的变换$$\bm{G}$$

> 现在我们的目标是要**反着来**，求$$\bm{G}^T$$

1) 最后一步**原先**既然是$$\dfrac{1}{\bm{Q}[0, n)}$$，那么此时我第一步就应该是
```math
\displaystyle
\dfrac{1}{\bm{Q}^T[0, n)}\bm{a}
```
即$$\times \dfrac{1}{\bm{Q}^T[0, n)}$$

2) 考虑**线段树分治**的递归过程，**原来**我们是自底向上合并
现在呢？就应该是**自顶向下**求解，**叶子结点**就是答案，比如$$\bm{ans} = \bm{ga}$$
那么$$\bm{A}(x_i) = ans[i]$$

具体来说，假设说现在线段树的点`node`上，原先是
```math
\displaystyle
\bm{P}_{node} = \bm{Q}
\begin{pmatrix}
P_L \\
P_R
\end{pmatrix}
```
现在假设说递归到`node`处，求出来的中间状态对应的多项式是$$\bm{P}'\_{node}$$
```math
\displaystyle
\begin{pmatrix}
P_L' \\
P_R'
\end{pmatrix}
= \bm{Q}^T P'_{node}
```
这是对应上述递归变换的逆过程，而
```math
\displaystyle
\bm{Q}^T =
\begin{pmatrix}
Q_R^T \\
Q_L^T
\end{pmatrix} \\
\quad \\
\begin{pmatrix}
P_L' \\
P_R'
\end{pmatrix}
= \begin{pmatrix}
Q_R^T \\
Q_L^T
\end{pmatrix} P'_{node}
```
递归的时候
```math
\displaystyle
P_L' = Q_R^T P'_{node} , \quad P_R' = Q_L^T P'_{node} 
```
**注意**
这里的$$P\_{node}', P\_L', P\_R'$$并不是原问题中的$$P\_{node}, P\_L, P\_R$$
而是多点求值在递归的过程中产生的**中间状态**

原问题中，我们并没有（也不需要）把$$P\_L, P\_R, P\_{node}$$的值给求出来
只需要分析一下具体的变换过程，然后**倒着做一遍**
具体我们要求的，实际上一直都是$$P\_{node}', P\_L', P\_R'$$

3）最后叶子结点就是答案

**算法实现**
```bash
    std::vector<cd> eval(std::vector<cd> x) const {
        if (size() == 0) return std::vector<cd>(x.size(), cd(0, 0));

int n = std::max<int>(int(x.size()), size());
        std::vector<Poly> q(4 * n);
        std::vector<cd> ans(x.size());

x.resize(n);

// [l, r)
        std::function<void(int, int, int)> build = [&](int p, int l, int r) -> void {
            if (r - l == 1) {
                // 分母，(1 - x[l])
                q[p] = Poly{cd(1, 0), -x[l]};
                return;
            }
            int m = (l + r) >> 1;
            build(p<<1, l, m);
            build(p<<1|1, m, r);
            q[p] = q[p<<1] * q[p<<1|1];
        };
        // 预处理分母 Q[0, n)
        build(1, 0, n);

std::function<void(int, int, int, const Poly&)> work = [&](int p, int l, int r, const Poly &num) {
            if (r - l == 1) {
                if (l < int(ans.size())) {
                    ans[l] = num[0];
                }
            }
            else {
                int m = (l + r) >> 1;
                work(p<<1, l, m, num.mulT(q[p<<1|1]).modxk(m - l));
                work(p<<1|1, m, r, num.mulT(q[p<<1]).mulxk(r - m));
            }
        };
        work(1, 0, n, mulT(q[1].inv(n)));
        return ans;
    }
```

看完文章有啥想法

算法小站

wiki 主题

数学

多项式与形式幂级数

目录