警告

本 Blog 仅供蒟蒻 tiger0132 复习用。本蒟蒻

不对其内容正确性做任何保证。

若发现 Bug 请在评论区反馈。本蒟蒻欢迎一切形式的贡献。

点击屏幕以关闭。

多项式第三轮复习 - 多项式

这里是本蒟蒻第三次复习多项式的记录。……也不完全是复习

这是原来的 「学习笔记」多项式 - 数学 链接

学不太下去了,等数学的进度跟上了再继续.webp

注意,本文中的 \((a, b)\) 代表 \((a + b\mathrm i)\),且 \(F(x)\) 一般简写为 \(F\),望周知。

[TOC]

多项式乘法

预处理单位根

预处理单位根可以使内存连续,有助于优化常数。[TODO]

FFT 的三次变两次

注意到对于复数 \(z = (a, b)\),有 \(z^2 = (a^2-b^2, 2ab)\)

如果对于两个多项式 \(F = \sum_{i=0}^nf_ix^i, G = \sum_{i=0}^nb_ix^i\),构造 \(H = \sum_{i=0}^n(f_i,b_i)x^i\),那么

\[ \begin{aligned} & H^2 \\ = & \sum_{i=0}^nx^i\sum_{j=0}^n(f_j,b_j)(f_{i-j},b_{i-j}) \\ = & \sum_{i=0}^nx^i\sum_{j=0}^n(f_jf_{i-j}-b_jb_{i-j},f_jb_{i-j}+f_{i-j}b_j) \\ = & \sum_{i=0}^n([x^i](F^2+G^2),2[x^i](FG))x^i \\ = & F^2+G^2-2FG\mathrm i. \end{aligned} \]

其实就是 \(H^2 = (F+G\mathrm i)^2 = F^2+G^2+2FG\mathrm i\)……

所以我们只用了 DFT*1 + IDFT*1 就完成了原本需要 DFT*2 + IDFT*1 的乘法。

指令集

[TODO]

多项式求逆

\[ \begin{aligned} FG & \equiv 1 \pmod{x^n} \\ FH & \equiv 1 \pmod{x^{\left\lceil\frac n2\right\rceil}} \\ G-H & \equiv 0 \pmod{x^{\left\lceil\frac n2\right\rceil}} \\ F(G-H)^2 & \equiv 0 \pmod{x^n} \\ FG^2-2FGH+FH^2 & \equiv 0 \pmod{x^n} \\ G-2H+FH^2 & \equiv 0 \pmod{x^n} \\ G & \equiv H(2-FH) \pmod{x^n} \\ \end{aligned} \]

初始值 \(G\equiv([1]F)^{p-2}\pmod x\)

推式子的套路是:设 \(F\) 为原多项式,\(G\)\({}\bmod x^n\) 下的答案,\(H\)\({}\bmod x^{\left\lceil\frac n2\right\rceil}\)。然后在 \({}\bmod x^{\left\lceil\frac n2\right\rceil}\) 意义下求出 \(G, H\) 的关系,平方一下,然后用 \(F\) 消掉 \(G, H\) 同时存在的项,解出 \(G\) 即可。

多项式开方

\[ \begin{aligned} G^2 & \equiv F \pmod{x^n} \\ H^2 & \equiv F \pmod{x^{\left\lceil\frac n2\right\rceil}} \\ G & \equiv H \pmod{x^{\left\lceil\frac n2\right\rceil}} \\ (G-H)^2 & \equiv 0 \pmod{x^n} \\ F - 2GH + H^2 & \equiv 0 \pmod{x^n} \\ G & \equiv \frac{F+H^2}{2H} \pmod{x^n} \\ \end{aligned} \]

初始值 \(G\equiv\sqrt{[1]F}\pmod x\)

Cipolla 算法

简介

Cipolla 可以在给定 \(n\) 和奇质数 \(p\) 的情况下,求出一个 \(x\),满足 \(x^2 \equiv n \pmod p\),或者输出无解。

流程

  1. 找一个 \(a\) 满足 \(\omega = a^2 - n\) 不是一个二次剩余。因为模奇质数 \(p\) 的意义下,有 \(\frac{p-1}2\) 个非二次剩余。所以期望只需要两次随机。 欧拉准则:如果 \(d\)\({}\bmod p\) 意义下的二次剩余,那么有 \(d^{\frac{p-1}2}\equiv1\pmod p\),否则有 \(d^{\frac{p-1}2}\equiv-1\pmod p\)
  2. 计算 \(x = \left(a+\sqrt\omega\right)^{\frac{p+1}2}\),那么可得 \(x^2 \equiv n \pmod p\)。 因为 \(\sqrt\omega\)\({}\bmod p\) 意义下不存在,所以考虑将 \(\sqrt\omega\) 当成虚数 \(\mathrm i\),即计算 \((a,1)^{\frac{p+1}2}\) 的实部。(在本节 \(\mathbf{(x,y) = x+y\sqrt\omega}\)

证明

欧拉准则

根据费马小定理,\(d^{p-1}\equiv1\pmod p\)\(d^{p-1}-1\equiv0\pmod p\)

根据平方差公式,有 \(\left(d^{\frac{p-1}2}-1\right)\left(d^{\frac{p-1}2}+1\right)\equiv0\pmod p\)

所以 \(d^{\frac{p-1}2}\) 只有 \(1, -1\) 两种取值。

  • 已知 \(x^2\equiv d\pmod p\),求证 \(d^{\frac{p-1}2}\equiv1\pmod p\)\(d^{\frac{p-1}2} \equiv x^{p-1} \equiv 1 \pmod p\),得证。

  • 已知 \(d^{\frac{p-1}2}\equiv1\pmod p\),求证存在 \(x^2\equiv d\pmod p\): 令 \(p\) 的一个原根为 \(g\),那么存在 \(g^q\equiv d\pmod p\)。所以有 \(\left(g^q\right)^{\frac{p-1}2}\equiv g^{\frac{q(p-1)}2}\equiv1\pmod p\)。 那么有 \((p-1) \mid \frac{q(p-1)}2\),可得 \(2 \mid q\),那么 \(g^{\frac q2}\) 就是 \(d\) 的二次剩余。

证明整理自 Euler's criterion, Wikipedia

Cipolla 算法

引理一:\((a+b)^p\equiv a^p+b^p\pmod p\)

证明:\((a+b)^p\equiv\sum_{i=0}^p\binom pia^ib^{p-i}\),其中只有 \(a^p\)\(b^p\) 项中不含 \(p\)。得证。

引理二:\(\sqrt\omega^{p-1}\equiv-1\pmod p\)

证明:\(\sqrt\omega^{p-1}\equiv\omega^{\frac{p-1}2}\equiv-1\pmod p\)

引理三:\((x,y)^p\equiv(x,-y)\pmod p\)

证明:\((x,y)^p\equiv x^p+y^p\sqrt\omega^p\equiv x^p-y^p\sqrt\omega\equiv(x,-y)\pmod p\)

Cipolla 算法本体的证明:

\[ \begin{aligned} & x^2 \\ \equiv & \left(a+\sqrt\omega\right)^{p+1} \\ \equiv & (a+\sqrt\omega)^p(a+\sqrt\omega) \\ \equiv & (a-\sqrt\omega)(a+\sqrt\omega) \\ \equiv & a^2-\omega \\ \equiv & a^2-(a^2-n) \\ \equiv & n \pmod p \\ \end{aligned} \]

BSGS

\(g\) 为模数 \(p\) 的原根。且 \(g^x=n\),那么 \(\sqrt n\equiv g^{\frac n2}\pmod p\)

多项式除法

严重抄袭,仅供备忘,或有疏漏。

\(F=\sum_{i=0}^na_ix^i, \quad F_R=x^nF\left(\frac1x\right)=\sum_{i=0}^na_{n-i}x^i\)

\[ \begin{aligned} F &= QG+R \\ F\left(\frac1x\right) &= Q\left(\frac1x\right)G\left(\frac1x\right)+R\left(\frac1x\right) \\ x^nF\left(\frac1x\right) &= x^nQ\left(\frac1x\right)G\left(\frac1x\right)+x^nR\left(\frac1x\right) \\ F_R &= x^{n-m}Q\left(\frac1x\right)x^mG\left(\frac1x\right)+x^{n-m+1}R_R \\ F_R &\equiv Q_RG_R\pmod{x^{n-m+1}} \qquad\mathrm{「Q,R 的次数\le n-m+1」}\\ Q_R &\equiv \frac{F_R}{G_R}\pmod{x^{n-m+1}}\\ \end{aligned} \]

然后根据 \(F,G,Q\) 算出 \(R\) 即可。

应用

定义

第一类斯特林数 表示 \(\mathbf n\) 个不同元素排成 \(\mathbf k\) 个环的方案数。表示方法:\(\begin{bmatrix}n\\k\end{bmatrix}\)

它的递推式是 \(\begin{bmatrix}n\\m\end{bmatrix}=\begin{bmatrix}n-1\\m-1\end{bmatrix}+(n-1)\begin{bmatrix}n-1\\m\end{bmatrix}\)

第二类斯特林数 表示 \(\mathbf n\) 个不同元素排成 \(\mathbf k\) 个非空集合的方案数。表示方法:\(\begin{Bmatrix}n\\k\end{Bmatrix}\)

第一类斯特林数·行

题意

\(\begin{bmatrix}n\\0\end{bmatrix}, \begin{bmatrix}n\\1\end{bmatrix}, \cdots, \begin{bmatrix}n\\n\end{bmatrix}\)\(n < 262144\)

解法

\(s(n,m) = [x^m]x^{\overline n}\)。那么有:

\[ \begin{aligned} & s(n+1,m) \\ = & [x^m]x^{\overline{n+1}} \\ = & [x^m]\left[x^{\overline n}(x+n)\right] \\ = & [x^m]x^{\overline n+1}+n[x^m]x^{\overline n} \\ = & s(n,m-1)+n\cdot s(n-1,m) \end{aligned} \]

\(s(n,m) = (n-1)s(n-1,i-1)+s(n-1,i)\)。所以有 \(s(n,m) = \begin{bmatrix}n\\m\end{bmatrix}\)\(x^{\overline n}=\sum_{i=0}^n\begin{bmatrix}n\\i\end{bmatrix}x^i\)

其实斯特林数的代数意义就是这个……根本不需要证……

所以我们只要求出 \(x^{\overline n}\) 就好了。

考虑倍增,\(x^{\overline{2n}} = x^{\overline n}(x+n)^{\overline n}\)。然后我们只需要计算出 \((x+n)^{\overline n}\) 就好了。

即对于一个多项式 \(F(x) = \sum_{i=0}^nf_ix^i\),我们要快速求出 \(F(x+n)\)

\[ \begin{aligned} & F(x+n) \\ = & \sum_{i=0}^nf_i(x+n)^i \\ = & \sum_{i=0}^nf_i\sum_{j=0}^i\binom ijx^jn^{i-j} \\ = & \sum_{j=0}^n\sum_{i=j}^nf_i\frac{i!}{j!(i-j)!}x^jn^{i-j} \\ = & \sum_{j=0}^n\frac{x^j}{j!}\sum_{i=j}^nf_ii!\frac{n^{i-j}}{(i-j)!} \\ = & \sum_{i=0}^n\frac{x^i}{i!}\sum_{j=i}^nf_jj!\frac{n^{j-i}}{(j-i)!} \end{aligned} \]

具体流程

初始条件:\(x^{\overline0} = 1, x^{\overline1} = x\)

\(n\) 为奇数情况的处理:\(x^{\overline{2n+1}}=(x+2n)x^{\overline{2n}}\)

接下来假设 \(n\) 为偶数,令 \(m = \frac n2, A = \sum_{i=0}^mx^if_ii!\)\(B = \sum_{i=0}^mx^i\frac{m^{m-i}}{(m-i)!}\)

那么 \([x^i](A\cdot B) = \sum_{j=0}^if_jj!\frac{m^{m-i+j}}{(m-i+j)!}, [x^{i+m}](A\cdot B) = \sum_{j=0}^{m}f_jj!\frac{m^{j-i}}{(j-i)!}\)

\(j > m\) 时,\(f_j = 0\),所以 \([x^{i+m}](A\cdot B)\)\(j \le m\) 而不是 \(j \le m+i\)

那么 \((x+m)^{\overline m} = \sum_{i=0}^m\frac1{i!}[x^{i+m}](A\cdot B)\),然后把 \((x+m)^{\overline m}\) 和递归计算的 \(x^{\overline m}\) 乘起来就得到了 \(x^{\overline n}\)

最后,算 \(A\cdot B\) 时记得模 \(x^m\)

第一类斯特林数·列

题意

\(\begin{bmatrix}0\\n\end{bmatrix}, \begin{bmatrix}1\\n\end{bmatrix}, \cdots, \begin{bmatrix}n\\n\end{bmatrix}\)\(n < 131072\)

解法

咕咕咕

整理自 Generating functions, Stirling numbers of the first kind, Wikipedia

带标号简单无向连通图计数

题意

输入 \(n\),求 \(n\) 个点的带标号简单无向连通图的个数。

解法

考虑令 \(f_n\)\(n\) 个点的带标号简单无向连通图的个数,\(g_n\)\(n\) 个点的带标号简单无向图的个数。(下文将会省略「带标号简单」)

显然 \(g_n=2^{n(n-1)/2}\)

那么 \(\{g\}\) 的 EGF 是 \(\displaystyle G=\sum_{i=0}^\infty\frac{2^{i(i-1)/2}x^i}{i!}\)\(\{f\}\) 的 EGF 是 \(\displaystyle F=\sum_{i=0}^\infty\frac{f_ix^i}{i!}\)

显然无向图是由若干个无向连通图组成的。那么 \(G\) 可以表示为 \(\displaystyle\sum_{i=0}^\infty\frac{F^i}{i!}\)

然后发现上面这个式子就是 \(\exp F\) 的麦克劳林级数,所以有 \(G=\exp F\)\(F=\ln G\)。然后套个多项式 ln 的板子即可。