数↑学↓技~巧~——多项式、方程与极值选讲
Acheron_RBM
·
·
算法·理论
1.求↑导↓技\~巧\~
普通的求导相信大家都会，不会的直接跳到 2，我们来讲多元带限制多项式极值怎么求。
有几种方法，不等式自然不在我们的考虑范围内（实际上是我不会）我们考虑直接使用拉格朗日乘数法。
定义目标函数 f(x_1,...,x_n) 以及约束 g(x_1,..,x_n)=0，我们现在 g 成立的情况下求 f 的极值。
首先不难发现，在约束曲面 g(x_1,...,x_n)=0 上，极值点必要的条件就是二者（目标函数与约束函数）梯度平行。
感性理解：
此时引入拉格朗日乘数 $\lambda$ 则有：
$$
\nabla f=\lambda \nabla g
$$
此时构造 $L(x_1,..,x_n,\lambda)=f(x_1,...,x_n)+\lambda g(x_1,...,x_n)$ 分别求每个变量的偏导并全部令其等于 0 求解即可。
同理的，如果限制有很多个（假设有 $k$ 个，$g_1,...,g_k$）那就构造：
$$
L(x_1,..,x_n,\lambda_1,...,\lambda_n)=f(x_1,...,x_n)+\sum_{i=1}^{k} \lambda_i g_i(x_1...x_n)
$$
小技巧：
1. 对于轮换对称的 $f$ 和 $g$（定义域是实数），我们直接令所有变量相等带入 $g$ 解方程即可，证明简单，读者自证不难。
2. 求解方程组的时候，试着用其他变量表示 $\lambda$（当然不只是 $\lambda$，也可以是只有 $\lambda$ 一个变量的式子，但是此后每个方程都要化成这个式子），而不是解一个然后往下代（自己计算对比一下两种方法即可）。
接下来问题来了，怎么验证（你不知道求出来的是最大值还是最小值还是鞍点）但是说实话，这个其实不重要，因为题目让你求最大值你求的就是最大值（多个解就取最大的）不存在无法判断的问题。
我们看看一元函数求导完是怎么操作的，直接回代求二阶导，但是多元函数显然不行。
（为了方便书写，$x$ 均指一组解）
设约束为：
$$
g_i(x) = 0,\quad i=1,...,m
$$
构造拉格朗日函数：
$$
L(x,\lambda) = f(x) + \sum_{i=1}^m \lambda_i g_i(x)
$$
在求出候选点 $(x_0,\lambda_0)$ 后：
先求：
$$
d^2L = \sum_{j,k} \frac{\partial^2 L}{\partial x_j \partial x_k}(x_0,\lambda_0)\, dx_j\, dx_k
$$
这里的 Hessian 是对 $x$ 变量的二阶偏导矩阵。
切空间由线性化约束给出：
$$
\sum_{j} \frac{\partial g_i}{\partial x_j}(x_0) \, dx_j = 0,\quad i=1,\dots,m
$$
这些条件限制了允许的 $(dx_1,\dots,dx_n)$ 方向。
- 如果在所有满足切空间条件的非零 $dx$ 上，$d^2L > 0$，则是极小值。
- 如果在所有满足条件的非零 $dx$ 上，$d^2L < 0$，则是极大值。
- 如果有的方向正、有的方向负，则无极值。
例子不举了，自己试试看。
给一道例题，当 $a^3+b^3+6ab=8$ 时，求 $a+b$ 取值范围。
### 2.代↑入↓技\~巧\~
这个内容很简单的，绝对是初等。（
考虑这样一个问题一个二次函数（绝对值有最大值限制，变量 $x$ 也有限制），系数全部未知，想一个关于系数的绝对值多项式的最大值。
乍一看不好做，实际上很简单。
我们发现一个二次函数在闭区间上的最值要么在对称轴上要么在端点，设这三个数为 $u,v,w$ 很容易用 $a,b,c$ 表示，这样我么就得到了一个关于这六个变量的六元一次方程组。
回带到目标函数即可。
Q：为什么要这么换元？
A：因为换完的 $u,v,w$ 有限制，而 $a,b,c$ 本身没有显性的性质。
例题：当 $x \in [-1,1]$ 时 $|ax^2+bx+c| \le 1$ 求 $2|a|+|b|+3|c|$ 的最大值。
### 3.置↑换↓技\~巧\~
你有没有遇到这样的题目，$A=\{1,...,n\}$，$f:A\rightarrow A$ 是双射，满足 $f(f(f(x)))=x$，$x \in A$，求映射个数。
（直接做组合意义即可，但是我不想）
~~正常人~~看到这个都能想到和 GF 或者递推有点关联。
我们先不用：
虽然本题不是典型的“群作用”问题，但可以构造一个作用来用 Burnside 引理：
让循环群 $C_3 = \langle g \rangle$ 作用在 $S_n$ 上，作用方式是“左乘”或“共轭”某个固定的 3 次幂运算。
固定点就是满足 $f^3 = \mathrm{id}$ 的元素。
用数固定点的公式算即可。
但是你发现了没有，这里我们有个限制啊，就是 $f$ 的阶，整除 3。
所以直接分类讨论，全不动，一个三循环剩下不动，……以此类推。
用公式即可计数。
或者考虑生成函数。
允许的循环长度集合 $L = \{1,3\}
其 EGF：\exp\!\big(x + \frac{x^3}{3}\big)
提取系数：
A_n = \sum_{b=0}^{\lfloor n/3 \rfloor} \frac{n!}{(n-3b)!\,b!\,3^b}
带入即可。
或者不提取系数，微分方程搞个递推：
由 EGF P(x) = \exp(x + x^3/3) 可得微分方程：
P'(x) = (1 + x^2) P(x)
对比系数得到递推：
A_{n+1} = A_n + n(n-1) A_{n-2}, \quad A_0=1, A_1=1, A_2=1
结束，小的 n 建议用 Burnside 引理后面跟着的那个分类法。
4.C↑B↓技巧
（这里的 CB 指的是切比雪夫多项式）
首先切比雪夫多项式最直接的应用就是它是 Sturm-Liouville理论中特殊的微分方程的解。
不过先看定义：
切比雪夫多项式是正交多项式，分为两类：
- 第一类： T_n(x)
- 第二类： U_n(x)
它们最初源于多倍角公式：
T_n(\cos\theta) = \cos(n\theta), \quad
U_n(\cos\theta) = \frac{\sin((n+1)\theta)}{\sin\theta}
第一类：
T_0(x) = 1,\quad T_1(x) = x
T_{n+1}(x) = 2xT_n(x) - T_{n-1}(x)
第二类：
U_0(x) = 1,\quad U_1(x) = 2x
U_{n+1}(x) = 2xU_n(x) - U_{n-1}(x)
$n$ 偶时为偶函数，$n$ 奇时为奇函数。
零点（第一类）：
$$
x_k = \cos\frac{(2k-1)\pi}{2n},\quad k=1,\dots,n
$$
这些点就是切比雪夫节点。
极值点:
- 在 $x_k^* = \cos\frac{k\pi}{n}$ 处交替取 $\pm 1$。
当然，根据定义，其满足正交性：
在权函数 $w(x) = \frac{1}{\sqrt{1-x^2}}$ 下：
$$
\int_{-1}^1 T_m(x)T_n(x) w(x) \, dx =
\begin{cases}
0, & m\ne n \\
\pi, & n=0 \\
\frac{\pi}{2}, & n\ge 1, m=n
\end{cases}
$$
试着推导一下其的显示多项式：
定义：
$$
T_n(\cos\theta) = \cos(n\theta)
$$
利用棣莫弗公式：
$$
(\cos\theta + i\sin\theta)^n = \cos(n\theta) + i\sin(n\theta)
$$
取实部：
$$
\cos(n\theta) = \sum_{k=0}^{\lfloor n/2 \rfloor} (-1)^k \binom{n}{2k} \cos^{\,n-2k}\theta \, \sin^{2k}\theta
$$
令 $x = \cos\theta$，则：
$$
\sin^{2k}\theta = (1 - x^2)^k
$$
代入上式：
$$
T_n(x) = \sum_{k=0}^{\lfloor n/2 \rfloor} (-1)^k \binom{n}{2k} x^{\,n-2k} (1 - x^2)^k
$$
整理得：
$$
T_n(x) = \sum_{k=0}^{\lfloor n/2 \rfloor} (-1)^k \binom{n}{2k} (1 - x^2)^k \, x^{\,n-2k}
$$
这个时候就该问了，有啥应用呢？
其实挺多的，回到最开始提到的微分方程，容易发现 $T_n(x)$ 是：
$$
(1-x^2) y'' - x y' + n^2 y = 0
$$
的解，证明简单，留给读者。
还有可以在线性的复杂度内算出 $T_{0}(x),...,T_n(x)$。
切比雪夫多项式满足一个多项式 Pell 方程：
$$
T_n(x)^2 - (x^2 - 1) U_{n-1}(x)^2 = 1
$$
这和经典 Pell 方程 $a^2 - D b^2 = 1$ 完全平行，只不过这里的系数在多项式环 $\mathbb{R}[x]$ 中。
在环 $\mathbb{R}[x, \sqrt{x^2-1}]$ 中，元素
$$
T_n(x) + U_{n-1}(x)\sqrt{x^2-1}.
$$
是单位元，且它们构成一个同构于 $(\mathbb{Z},+)$ 的无限循环群：
$$
(T_m + U_{m-1}\sqrt{x^2-1}) \cdot (T_n + U_{n-1}\sqrt{x^2-1}) = T_{m+n} + U_{m+n-1}\sqrt{x^2-1}
$$
故切比雪夫多项式是多项式 Pell 方程单位群的幂次结构的显式描述。
在群代数 $\mathbb{R}[C_\infty]$ 中，若设 $g$ 是生成元，定义 $x = \frac{g+g^{-1}}{2}$，那么：
$$
g^n + g^{-n} = 2 T_n(x)
$$
在我的印象里，似乎和 $sl_2$ 也是有关系的。
### 5.插↑值↓\~技\~巧
先提两句拉插的核心。
初中三年级的时候我们就学过待定系数法求解二次函数的解析式。
但是如果给定的点数大于三个，我们实际上是不知道它在一个什么样的函数上的。
这个时候就有了插值方法。
考虑每一个点 $(x,y)$，如果构造一个函数，使得其在这个点 $x$ 对应的值是1，其他的 $x$ 对应值为 0（就是当前点的 $x$ 对应的 $y$ 为 1，其他的都是0），实际上最后的函数就是构造的所有函数乘上其对应的 $y$ 相加。
根据上述推导，我们有如下定义：
$$
P(x) = \sum_{i=0}^n y_i \cdot \ell_i(x), \quad
\ell_i(x) = \prod_{\substack{0 \le j \le n \\ j \ne i}} \frac{x - x_j}{x_i - x_j}
$$
实际上点一多就不好算了，所以这一章主要介绍几个技巧能让手算变得更好算（优化时间复杂度不用我讲了吧）。
1. 先算好分母，把所有小函数的分母先算出来，尤其是在给定点不是整点的时候。
2. 如果节点是 $x_0, x_1, \dots, x_n$，要算某个 $x$ 的插值值：先算前缀积：$pre[k] = \prod_{j=0}^{k-1} (x - x_j)$ 再算后缀积：$suf[k] = \prod_{j=k+1}^{n} (x - x_j)$ 那么分子 $\prod_{j\ne i}(x - x_j) = pre[i] \cdot suf[i]$ 这样每个分子只需一次乘法，不用重复全乘，前提最好是整点。
3. 其实解析法都不是给你拿去爆算的，还是要观察点的排列，比如对称之类的。
还有一个方法是重心：
重心公式：
$$
P(x) = \frac{\sum_{i=0}^n \frac{w_i y_i}{x - x_i}}{\sum_{i=0}^n \frac{w_i}{x - x_i}}, \quad w_i = \frac{1}{\prod_{j\ne i}(x_i - x_j)}
$$
~~本来要写 KTT+凸分析去做不等式约束的极值的，但是我不太会，而且没想到什么很好的结论就算了。~~