Chlience

【其他】LLX的数论讲堂 笔记
多项式及其应用多项式的数域对于数域$F$,若$a_0 , a_1 , a_2 , \cdots , a_n \in F$
扫描右侧二维码阅读全文
07
2018/11

【其他】LLX的数论讲堂 笔记

多项式及其应用

多项式的数域

对于数域$F$,若$a_0 , a_1 , a_2 , \cdots , a_n \in F$

$$ f(x)=\sum_{i=0}^{n}a_ix_i $$

为数域$F$上的一个多项式
其数域$F$上的所有多项式记作$F[x]$

同样的
$Q[x]$为有理数域的所有多项式
$R[x]$为实数域的所有多项式
$C[x]$为复数域的所有多项式

多项式的度数

多项式最高非零项的次数成为多项式的度数,用$\deg$表示

$$ f(x) = \sum_{i = 0}^{n} a_i x^i $$

其中$a_i\neq 0$
记作$\deg f(x)=n$

首一多项式(略)

加法与数乘运算(略)

多项式的线性空间

线性空间,即向量空间
满足线性性,封闭性
线性性: 量与量之间按比例呈线性的关系
封闭性: 其两个集合内元素进行二元运算结果必然在集合内

显然多项式加法,数乘运算满足线性性
记$F_n[x]$表示数域$F$上度数不超过$n$的全体多项式的集合,显然它们构成一个线性空间

多项式与向量满足一一对应的双射关系

$$ f(x)=\sum_{i = 0} ^ {n}a_ix^i \Leftrightarrow \vec{a}=(a_0 , a_1 , \cdots , a_n) $$

多项式的系数表达

用一个$n+1$维的向量来表示$F_n[x]$中的全体多项式

多项式乘法

$$ f(x)=\sum_{i=0}^{n}a_ix_i $$

$$ g(x)=\sum_{i=0}^{n}b_ix_i $$

$$ h(x) = f(x)*g(x)=\sum_{i=0}^{2*n}\sum_{j=0}^{i}a_jb_{i-j}x^i $$

向量的卷积

多项式乘法中将多项式用向量表示其系数关系就是向量的卷积

$$ f(x)=\vec{a} $$

$$ g(x)=\vec{b} $$

$$ h(x)=\vec{c}=\vec{a}\otimes\vec{b} $$

$$ c_i=\sum_{j=0}^{i}a_j b_{i-j} $$

多项式的幂

$$ f^{k}(x)=\prod_{i=1}^{k}f(x) $$

多项式的复合

$$ (f \circ g)(x)=f(g(x))=\sum_{i=0}^{n}a_ig^{i}(x) $$

多项式的分治乘法

设$n$为$2$的自然数次幂,即$\exists k\in N,n=2^k$
设$f,g\in F_{2n-1}[x]$(一共有2n项)
将其分为两半

$$ f(x)=f_0(x)+x^nf_1(x) $$

$$ g(x)=g_0(x)+x^ng_1(x) $$

显然的,$f_0,f_1,g_0,g_1\in F_{n-1}[x]$

$$ (f \times g)(x) = (f_0 \times g_0)(x) +x_n(f_0 \times g_1 +f_1 \times g_0)(x) + x_{2n}(f_1 \times g_1)(x) $$

观察中间项,$(f_0 \times g_1 +f_1 \times g_0)(x)=((f_0+f_1)\times(g_0 + g_1) - f_0 \times g_0 - f_1 \times g_1)(x)$
那么我们就只需要处理$(f_0 \times g_0)(x) , (f_1 \times g_1)(x) , ((f_0 +f_1) \times (g_0 + g_1))(x)$,规模均为原问题的一半
所以$T(n)=3T(\frac{n}{2})+O(n)=O(n^{log_23})\approx O(n^{1.585})$

多项式的点值表达

$$ \deg f(x) = n $$

$$ x_0 , x_1 , x_2 , \cdots , x_n \in F $$

$$ y_0 = f(x_0) , y_1 = f(x_1) , y_2 = f(x_2) , \cdots , y_n = f(x_n) $$

则$(x_0 , y_0) , (x_1 , y_1) , (x_2 , y_2) , \cdots ,(x_n , y_n)$为多项式$f(x)$的点值表达
点值表达与系数表达满足双射关系

有范德蒙德矩阵$V$

$$ \begin{pmatrix} 1 & x_0 & x_0^2 & \cdots & x_0^n\\ 1 & x_1 & x_1^2 & \cdots & x_1^n\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & x_n & x_n^2 & \cdots & x_n^n\\ \end{pmatrix} \begin{pmatrix} a_0\\ a_1\\ \vdots\\ a_n \end{pmatrix} = \begin{pmatrix} y_0\\ y_1\\ \vdots\\ y_n \end{pmatrix} $$

范德蒙德矩阵的行列式为$\prod_{j < i} (x_i - x_j)$
由于$x_i \neq x_j$,所以行列式值非零,有唯一解
在$x$确定时,$a,y$有一一对应的双射关系

多项式的点值乘法(略)

多项式的插值

给出多项式的点值表达,求多项式的系数表达

  1. 高斯消元$O(n^3)$
  2. 拉格朗日插值法$O(n^2)$

高斯消元(略)

拉格朗日插值法

$$ L(x)=\sum_{i=0}^{n}\frac{\prod_{j \neq i}x - x_j}{\prod_{j \neq i}x_i - x_j}y_i $$

不难发现$L(x_i) = y_i$
所以$L,f$有相同的系数表达

自然数幂级数和

自然数幂级数和记作$S$

$$ S(n,k)=\sum_{i = 0} ^ {n}i^k $$

$$ S(n,0) = n + 1 $$

//在这里我们将$0^0$看为$1$

$$ S(n,1) = \frac{n(n+1)}{2} $$

$$ S(n,2) = \frac{n(n+1)(2n+1)}{6} $$

合理推测
$S(n,k)$为$n$的$k+1$次多项式
为了计算$S(n,k)$
选择$x_i=i(i = 0,\cdots , k),y_i = S(x_i , k)$
插值求解即可

证明

$$ (n+1)^{k+1} - n^{k+1} = \sum_{i=0}^{k} \begin{pmatrix} k+1\\ i \end{pmatrix} n^i $$

$$ n^{k+1} - (n - 1) ^ {k+1} = \sum_{i=0}^{k} \begin{pmatrix} k+1\\ i \end{pmatrix} (n - 1)^i $$

$$ \vdots $$

$$ 1^{k+1}-0^{k+1}=\sum_{i=0}^{k} \begin{pmatrix} k+1\\ i \end{pmatrix} 0^i $$

累加得

$$ (n+1)^{k+1}=\sum_{i=0}^{k} \begin{pmatrix} k+1\\ i \end{pmatrix} S(n,i) $$

显然可得$S(n,k)$的度数

欧拉公式

$$ e^{i\theta}=cos(\theta)+isin(\theta) $$

几何意义上是单位圆上角度为$\theta$的点
Circle.png

单位复数根

考虑构造一个$x$,使得$x^n=1$
由欧拉公式可得$e^{2k\pi i}=1$
则$x^n = e^{2k\pi i} , x = e^{\frac{2k\pi i}{n}}$
当$k = 1$ 时,令$\omega_n=e^{\frac{2\pi i}{n}}$,称为主$n$次单位根
$w_n^k = e^{\frac{2k\pi i}{n}} = cos(\frac{2k\pi}{n}) + isin(\frac{2k\pi}{n})$
由三角函数的周期性$T=2\pi$,不难得到$w_n^k$的周期性
$w_n^k = w_n^{k\mod n}$
$w_n^n = w_n^0 = 1$
当$k=0,1,2,\cdots,n-1$时,得到$w_n^0,w_n^1,w_n^2,\cdots,w_n^{n-1}$,称为$n$次单位复数根

单位复数根的性质

消去引理:对于常数$d>0$,有$w_{dn}^{dk} = w_n^k$
折半引理:若$n$为偶数,则$n$次单位复数根的平方的集合就是$\frac{n}{2}$次单位复数根的集合。特别的,每个$\frac{n}{2}$次单位复数根出现两次
求和引理:

$$ \sum_{i=0}^{n-1}(w_n^k)^i= \begin{cases} n &n\mid k\\ 0 &n\nmid k \end{cases} $$

离散傅里叶变换(DFT)

多项式的系数表达式$f=(a_0,a_1,a_2,\cdots,a_{n-1})$,求出在$x_0 = w_n^0 , x_1 = w_n^1 , x_2 = w_n^2 , \cdots , x_{n-1} = w_n^{n-1}$初的点值

$$ y_k = f(x_k) = f(w_n^k) $$

输出向量$y=(y_0 , y_1 , y_2 , \cdots , y_{n-1})$
代入范德蒙德矩阵得:

$$ \begin{pmatrix} 1 & w_n^{0} & {w_n^{0}}^2 & \cdots & {w_n^{0}}^{n-1}\\ 1 & w_n^{1} & {w_n^{1}}^2 & \cdots & {w_n^{1}}^{n-1}\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & w_n^{(n-1)} & {w_n^{(n-1)}}^2 & \cdots & {w_n^{(n-1)}}^{n-1}\\ \end{pmatrix} \begin{pmatrix} a_0\\ a_1\\ \vdots\\ a_{n-1} \end{pmatrix} = \begin{pmatrix} y_0\\ y_1\\ \vdots\\ y_{n-1} \end{pmatrix} $$

此过程称为长度为$n$的离散傅里叶变换,记作$y = DFT_n(f)$
注意: 多项式的系数表达式的度数为$n-1$,而单位根为$n$次单位复数根

快速傅里叶变换(FFT)

$f = (a_0 , a_1 , a_ 2 , \cdots , a_{n-1})$
将奇数项,偶数项分别提出,得到构造出两个度为$\frac{n}{2}$的系数表示(假设$n$为偶数)
$f_0 = (a_0 , a_2 , a_4 , \cdots , a_{n-2})$
$f_1 = (a_1 , a_3 , a_5 , \cdots , a_{n-1})$

那么$f(x) = f_0(x^2) + x*f(1)(x^2)$

设$k < \frac{n}{2}$

$$ f(w_n^k) = f_0(w_2^{2k}) + w_n^k f_1(w_n^{2k}) = f_0(w_{\frac{n}{2}}^k) + w_n^k f_1(w_{\frac{n}{2}}^k) $$

$$ f(w_n^{k+\frac{n}{2}}) = f_0(w_n^{2k+n}) + w_n^{k+\frac{n}{2}} f_1(w_n^{2k+n}) = f_0(w_{\frac{n}{2}}^k) - w_n^k f_1(w_{\frac{n}{2}}^k $$

令$y_k = f(w_n^k) , y_k^{[0]} = f_0(w_{\frac{n}{2}}^k) , y_k^{[1]} = f_1(w_{\frac{n}{2}}^k)$
那么

$$ y_k = y_k^{[0]} + w_n^ky_k^{[1]} $$

$$ y_{k+\frac{n}{2}} = y_k^{[0]} - w_n^ky_k^{[1]} $$

这一系列操作称为蝴蝶操作,$w_n^k$称为旋转因子
每次递归求得$y_k^{[0]} , y_k^{[1]}$,问题规模变为$\frac{n}{2})$,合并得到$y_k$
$T(n)=2T(\frac{n}{2}) + O(n) = O(n\log n)$

逆离散傅里叶变换(IDFT)

多项式的点值表达式$(w_n^0 , y_0) , (w_n^1 , y_1) , (w_n^2 , y_2) , \cdots , (w_n^{n-1} , y_{n-1})$,转化为系数表达式

尝试求得范德蒙德矩阵的逆矩阵$V^{-1}$
即求$V_n V_n^{-1} = I_n$
即$v_i^{T}v_j^{-1} = \begin{cases} 1 &i=j\\0 &i\neq j\end{cases}$,其中$v_i^{T}$为$V$的行向量,$T$为转置,$v_j^{-1}$为$V^{-1}$的列向量

$v_i^{T} = (w_n^{0i} , w_n^{1i} , w_n^{2i} , \cdots , w_n^{(n-1)i})$
联系求和定理

$$ \sum_{i=0}^{n-1}(w_n^k)^i= \begin{cases} n &k = 0\\ 0 &k \neq 0 \end{cases} $$

那么构造$v_j^{-1} = \frac{1}{n}(w_n^{-0j} , w_n^{-1j} , w_n^{-2j} , \cdots , w_n^{-(n-1)j})^{T}$
验证:

$$ v_i^{T}v_j^{-1} = \frac{1}{n}\sum_{k = 0}^{n - 1}(w_n^{i-j})^k = \begin{cases} n &i=j\\ 0 &i\neq j\end{cases} $$

将$Va = y$同乘$V^{-1}$得$a = yV^{-1}$,即:

$$ \frac{1}{n} \begin{pmatrix} 1 & w_n^{-0} & {w_n^{-0}}^2 & \cdots & {w_n^{-0}}^{n-1}\\ 1 & w_n^{-1} & {w_n^{-1}}^2 & \cdots & {w_n^{-1}}^{n-1}\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & w_n^{-(n-1)} & {w_n^{-(n-1)}}^2 & \cdots & {w_n^{-(n-1)}}^{n-1}\\ \end{pmatrix} \begin{pmatrix} y_0\\ y_1\\ \vdots\\ y_{n-1} \end{pmatrix} = \begin{pmatrix} a_0\\ a_1\\ \vdots\\ a_{n-1} \end{pmatrix} $$

可见,$a$是系数表达$y = (y_0 , y_1 , y_2 , \cdots , y_{n-1})$的多项式在$w_n^0 , w_n^1 m, w_n^2 , \cdots , w_n^{n-1}$处取的的点值除以$n$
在这些位置求出点值的过程被称为逆离散傅里叶变换,记作$DFT_n^{-1}(y)$,只需要对前面的DFT稍加修改即可实现

卷积定理

设$a,b$为$n$维向量,$a,b$的卷积$c = a\otimes b$满足:

$$ c_i = \sum_{j = 0} ^{i} a_j \times b_{i-j} $$

通过多项式乘法与其系数表达卷积的关系可以得到:

$$ c = DFT_{2n}^{-1}(DFT_{2n}(a) \times DFT_{2n}(b)) $$

FFT的迭代实现

FFT.png
对于$n = 2^k$,考虑第$i$次分治(第$i$层)
二进制第$i$位为$0$,放入左侧,最终位置的第$k-i$位为$0$
二进制第$i$位为$1$,放入右侧,最终位置的第$k-i$位为$1$
不难发现,最终位置的二进制为原来位置的逆序

FFT题目:

BZOJ 3160 万径人踪灭
BZOJ 3527
BZOJ 4259 残缺的字符串
HDU 4609 3-idiots
codechef Prime Distance On Tree

剩余系

剩余系指对于某一个特定的正整数$n$,一个整数集中的数模$n$所得的余数域
如果一个剩余系中包含了这个正整数所有可能的余数,那么称之为模$n$的完全剩余系
简化剩余系是$n$的完全剩余系中与$n$互素的数构成的子集

群的阶数定义为集合$G$元素的个数,记作$|G|$
如果$G$只有有限个元素,称$G$为有限群
群的运算一般不可交换
满足交换律的群称为阿贝尔群(Abelian group)

模$n$的简化剩余系$Z_n^*$关于乘法构成的代数系统是群
封闭性:$gcd(ab , n) = gcd(ab\mod n , n) = 1$
结合律:乘法满足结合律
单位元:$e = 1$
逆元素:$ax\equiv 1\pmod n$在$Z_n^*$中有唯一解

子群

设$G$是群,$S$是$G$的一个子集,如果$S$仍然是群,或等价的满足
封闭性:$\forall a,b \in S , a * b \in S$
结合律:显然满足结合律
单位元:设$G$的单位元为$e$,有$e\in S$
逆元素:$\forall a \in S$,其在$G$中有逆元$a^{-1}$,$a^{-1}\in S$
则称$S$是$G$的一个子群
${e}$和$G$为$G$的平凡子群

陪集

设$H$为$G$的子群,$a \in G$,定义

$$ aH = {ah|h\in H} $$

称$aH$是$H$的一个左陪集

$aH = \{ah , | h\in H\}$
显然的陪集中的元素与子集中的元素满足双射关系
$f(x) = ax , f(x)^{-1} = a^{-1}x$

加上自己的一点理解?
$a\in G , a^{-1}\in G , x_1\in H , x_2\in H$
若$a * x_1 \equiv b \pmod n , a * x_2 \equiv b \pmod n$
则$b \in G , b * a^{-1} = x_1 = x_2$
所以子集中的元素乘$a$后并不会映射到同一个元素上
同理, 陪集中的元素不会映射到同一个元素上
所以满足双射关系(自己理解和上面式子无关)

$|aH| = |H|$
若$a\in H$,则$aH = H$

$(aH = bH) \vee (aH \cap bH = \emptyset)$
即$aH$和$bH$不可能既不等价,又有交集

证明:
若使得$aH \cap bH \neq \emptyset$
必然有$ah_1 = bh_2$
$a = h_2 * h_1^{-1} * b$
$aH = bH * h_2 * h_1^{-1} = bH$
$\forall g \in G , g \in gH$
$G \subseteq \bigcup_{a\in G}aH$
显然的$\bigcup_{a\in G}aH \subseteq G$
所以

$$ \bigcup_{a \in G}aH = G $$

即对于同一子集所形成的所有陪集的并等价于全集

陪集划分定理

假设有$a_1 , a_2 , \cdots , a_k \in G$
$G = \bigcup_{i = 1}^{k}a_iH$
其中$a_iH \cap a_jH = \emptyset (i\neq j)$

拉格朗日定理

根据陪集划分定理我们可以得到$k*|a_iH| = |G|$
即$k*|H| = |G| , |H| \mid |G|$

元素的幂

考虑有限群$G , a\in G$
元素的幂表示为$a^k = e\prod_{i=1}^{k}a , a^{-k} = e\prod_{i=1}^{k}a^{-1}$
使得$a_k = e$的最小正整数$d$称为$a$的阶,记作$ord(a)$
因为是个有限群,那么一定存在$ord(a)$

考虑由$a$的幂生成的集合$S = \{a_k|k\in Z\}$
显然$S$为$G$的子群
$|S| = ord(a) \Rightarrow ord(a) \mid |G|$
所以$a^{|G|} = a^{pord(a)} = (a^{ord(a)})^p = e^p = e$
$|Z_n^*| = \varphi(n)$
$\forall a\in Z_n^*$,(即$gcd(a , n) = 1$),有

$$ a^{\varphi(n)} = 1 \pmod n $$

原根

对于群$G$,若$\exists g\in G$,使得$ord(g)=|G|$,称$g$为$G$的原根
$G$中每一个元素都是$g$的幂次
因为$g^k$在模$n$意义下有$|G|$种取值
对应了$G$中的$|G|$个元素

$Z_n^*$ 存在原根 $\Leftrightarrow n = 2 , 4 , p^a , 2p^a$,其中$p$为奇素数
如果存在原根,原根的数目为$\varphi(\varphi(n))$

考虑这样的素数$p = c * 2^l + 1$
运算都在$Z_p^*$中进行
对于$n = 2^k (k\leq l)$,令

$$ g_n = g^{\frac{p - 1}{n}} $$

因为$p$为素数,所以$\varphi(p) = p - 1$,所以

$$ g_n^n = g^{p-1} = 1 $$

消去引理:$g_{dn}^{dk} = (g^{\frac{p-1}{dn}})^{dk} = (g^{\frac{p - 1}{n}})^k = g_n^k$
折半引理:$(g_n^k)^2 = (g_n^{k+\frac{n}{2}})^2 = g^{\frac{(p-1)k}{n}}$
求和引理:$\sum_{i = 0}^{n - 1} (g_n^k)^i = \begin{cases} n,n\mid k \\ 0,n\nmid k \end{cases}$
当$n\mid k$时,$g_n^k=(g^{\frac{p - 1}{n}})^{qn} = (g^{p - 1}) = 1$
当$n\nmid k$时,$g_n^k \neq 1 , \sum_{i = 0}^{n - 1} (g_n^k)^i = \frac{1 - g_n^{kn}}{1 - g_n^k } = 0$
可由等比数列递推公式得到

快速数论变换(NTT)

$g_n = g^{\frac{p - 1}{n}}$
$w_n = e^{\frac{2\pi i}{n}}$
$w_n \Leftrightarrow g_n$
将$DFT$修改为求$g_n^0 , g_n^1 , g_n^2 , \cdots , g_n^{n - 1}$处的点值
$IDFT$修改为求$g_n^0 , g_n^{- 1} , g_n^{- 2} , \cdots , g_n^{- (n - 1)}$处的点值

求原根

$g$为$Z_p^*$的原根$\Leftrightarrow ord(g) = p - 1$
由$ord(g) \mid (p - 1)$
设$p - 1$不同质因子为$p_1 , p_2 , \cdots , p_s$
$g$为原根$\Leftrightarrow g^{\frac{p - 1}{p_i}} \neq 1 , (i = 1 , 2 , \cdots , s)$

NTT中模数的选取

$c = a \otimes b$
$c_i = \sum_{j = 0} a_{i-j} b_j \pmod p$
如果$c_i < p$,显然结果是精确的
对于$p = c \times 2^k + 1$,必须满足$n \leq 2^k$
例:$p = 119*2^{23} + 1 = 998244353 , g = 3$

NTT题目

BZOJ 4555 求和

任意模数NTT(三模数NTT)

考虑长度为$n$($10^5$数量级)的向量在模$P$($10^9$数量级,可能非质数)意义下的卷积,即

$$ c_i = \sum_{j = 0}^{i}a_{i - j} b_j \mod P $$

NTT的模数需要满足条件$P = c*2^k + 1$,为质数
由于$P$甚至不是质数,难以直接NTT,尝试直接计算出最终结果
$nP^2$的数量级为$10^{23} > 2^{64}$
那么我们取$int$范围内较大的三个不同的满足NTT条件的质数$p_1 , p_2 , p_3$,使得$p_1p_2p_3 > nP^2$,并分别在模$p_i$意义下进行卷积。设真实值为$s$,可以得到:

$$ s \equiv s_1 \pmod {p_1} $$

$$ s \equiv s_2 \pmod {p_2} $$

$$ s \equiv s_3 \pmod {p_3} $$

前两项可以直接在$long long$范围内用CRT合并

$$ s \equiv s_0 \pmod {p_1p_2} $$

令$s = s_0 + kp_1p_2 = s_3 + lp_3$
注意到$k < p_3$,将上式放至模$p_3$意义下,有

$$ k \equiv (s_3 - s_0)(p_1p_2)^{-1} \pmod {p_3} $$

模$p_3$意义下所得即为$k$的真实值,随后在模$P$意义下回代得到$s\mod p$的值

形式幂级数

考虑无穷维的向量$f=(a_0 , a_1 , a-2 ,\cdots)$
看作是多项式的系数表达,可以的到其形式幂级数
$f(x) = \sum_{i = 0}^{\infty}a_i x^i$
$f'(x) = \sum_{i = 0}^{\infty}(i + 1) a_{i + 1} x_i$
$\int f(x)=\sum_{i=0}^{\infty}\frac{a_{i-1}}{i}x^i+C$
对$x^n$取模(取前$n$项):$f(x) = \sum_{i = 0}^{n - 1}x^i\pmod {x^n}$
加减乘幂复合等运算与有限多项式定义相仿

泰勒级数

$f(x) = \sum_{i = 0}^{\infty}\frac{1}{i!}f^{(i)}(x_0)(x-x_0)^i$,称为$f(x)$在$x = x_0$处的泰勒级数
当$x_0 = 0$时,$f(x) = \sum_{i = 0}^{\infty}\frac{1}{i!}f^i(0)x^i$,称为$f(x)$的麦克劳林(Maclaurin)级数
一般的初等函数其泰勒函数都在收敛域内收敛到原函数
$f(x) = \begin{cases}e^{-\frac{1}{x^2}},x\neq 0\\ 0,x=0\end{cases}$

牛顿迭代

对于$f(x)$在$x_0$的泰勒展开,观察一阶近似
$f(x) \approx f(x_0) + f'(x_0)(x - x_0)$
为了求$f(x)$的零点,考虑从$x_0 , f(x_0)$处作$f(x)$的切线,并取与$x$轴的焦点$x_1 = x_0 - \frac{f(x_0)}{f'(x_0)}$
取递推式$x_{n + 1} = x_n - \frac{f(x_n)}{f'(x_n)}$

多项式求逆

对于$f$,若有$g$,使得$f\times g(x) = 1$,称$g$为$f$的逆
给$f$,求$g$的前$n$项,即求$\frac{1}{f(x)}$的麦克劳林级数的前$n$项系数
例:$f(x) = 1 - x$
$g(x) = \frac{1}{1 - x} = \sum_{i = 0}^{\infty} x^i$
$f(x)$存在逆$\Leftrightarrow$常数项非0(否则就要出现$\frac{c}{0}$的情况)
考虑倍增,设$g_t$的前$2^t$位与$g$相同,其余位为$0$,显然有$(f\times g)(x) \equiv 0 \pmod {2^{t+1}}$
显然$g_{(t+1)}(x) - g_t(x)$的前$2^t$项为$0$,则$(g_{t+1}(x) - g_t(x))^2$的前$2^{t+1}$项为$0$,可得
$(g_{t+1}^2-2g_{t+1}g_{t}+g_t^2)(x)\equiv 0 \pmod {2^{t+1}}$
左乘$f(x)$,由$(f\times g_{t+1})(x)\equiv 1 \pmod {2^{t+1}}$
得到$(g_{t+1}-2g_t+f\times g_t^2)(x) \equiv 0 \pmod {2^{t+1}}$

$$ g_{t+1} = 2g_t - f \times g_t^2 $$

$$ g_0 = a_0^{-1} $$

$T(n) = T(\frac{n}{2}) + O(n \log n = O(n \log^2 n)$

多项式除法

已知$f,g,\deg f = n,\deg g = m (m \leq n)$
求唯一的$q,r$,使得$f = q \times g + r$,其中$\deg r < m$
例:$f(x) = x^4 + x^3 + 2x^2 + 4x + 2 , g(x) = x^2 + x +3$
$f(x) = (x^2 - 1)g(x) + 5x + 5$
其中$q(x) = x^2 + 1 , r(x) = 5x + 5$
$f = q \times g + r$
发现$r$的存在使得很不好进行运算,考虑消去$r$的影响
由于$\deg {q \times g} = \deg f$,将上式翻转,有
$f^R(x) = (q^R \times g^R)(x) + x^{n-\deg r}r^R(x)$
$R$指将多项式翻转
$\deg r \leq \deg g - 1 = m - 1\Rightarrow n - m - 1 \leq n - \deg r$
$x^{n - \deg r}r^R(x) \equiv 0 \pmod {x^{n-m-1}}$
$f^R(x) \equiv (q^R\times g^R)(x) \pmod{x^{n - m + 1}}$
至此,完全消去$r$的影响
此时对$g^R$求逆即可解出$q^R$,然后回代得到$r$
$T(n) = O(n \log n)$

多项式取对数

多项式的牛顿迭代

多项式开方

二次剩余

多项式求exp

多项式求幂

多项式的三角函数

生成函数

普通型生成函数(Ordinary Generation Function)

对于一个无穷数列$f_0 , f_1 , f_2 , \cdots$
将其看做一个无穷维向量,写出其形式幂级数:
$f(x) = \sum_{i = 0}^{\infty} f_i x^i$
例:数列$1,1,1,\cdots$的生成函数为:
$f(x) = 1 + x + x^2 + \cdots$
$x$没有实际含义(形式幂级数),故不考虑收敛域
二次项系数$C(a , 0) , C(a , 1), \cdots$生成函数为$(1 + x)^a$
设方程$e_1 + e_2 + \cdots + e_k = n$的非负整数解的方案为$h_n$,则$h_n$的生成函数为$e_1 , e_2 , \cdots , e_k$的生成函数的乘积
例:考虑$3e_1 + 4e_2 + 2e_3 + 5e_4 = n$的非负整数解的方案书数$h_n$的生成函数
令$f_1 = 3e_1 , f_2 = 4e_2 , f_3 = 2e_3 , f_4 = 5e_4$,得到
$f_1 + f_2 + f_3 + f_4$,且$f$的约束是:为上述关于$e$系数的倍数

$$ h(x) = (\sum_{i = 0}^{\infty} x^{3i})(\sum_{i = 0}^{\infty} x^{4i})(\sum_{i = 0}^{\infty} x^{2i})(\sum_{i = 0}^{\infty} x^{5i}) $$

$$ = \frac{1}{1 - x^3} \frac{1}{1 - x^4} \frac{1}{1 - x^2} \frac{1}{1 - x^5} $$

每一项的系数为取值,将加法转化为乘法

普通型生成函数题目

BZOJ 3028 食物

指数生成函数(Exponential Generation Function)

对于数列$f_0 , f_1 , f_2 , \cdots$,其指数型生成函数为
$f(x) = \sum_{i=0}^{\infty} \frac{f_i}{i!} x^i$
例:数列$1 , 1 , 1 , \cdots$的指数型生成函数为
$f(x) = \sum_{i = 0}^{\infty} \frac{1}{i!} x^i$
$f(x) = e^x$的麦克劳林级数为
$\sum_{i = 0}^{\infty}\frac{f^i(x)}{i!}x^i$
由自然对数性质可得$f^i(x) = e^x , f^i(0) = 1$
即$e^x = \sum_{i=0}^{\infty} \frac{1}{i!} x^i$
由$P_n^i = C_n^i * i!$
$P_n^0 , P_n^1 , P_n^2 , \cdots , P_n^n$的指数生成函数是$(1 + x)^n$

定义多重集的排列组合
$S = \{n_i · a_i\}(n_i = 0 , 1 , 2 ,\cdots , k)$,表示$S$集合中有$n_i$个$a_i$,$n_i$被称为元素$a_i$的重数,$k$称为多重集的类别数
多重集$S = \{n_i · a_i\}(n_i = 0 , 1 , 2 ,\cdots , \infty)$的$n$排列数的指数生成函数是

$$ \prod_{i}\sum_{j = 0}^{n_i} \frac{1}{j!} x^j $$

相当于$\infty$个全$1$数列指数生成函数的乘积
相当于是枚举对于每一个元素$a$,选择多少个,将其放入序列中有多少种不同的方法,最后求乘积和
最终答案为$n! *$($x^n$的系数)
结合$n$排列数公式$\frac{n!}{\prod_i m_i!}(\sum_i m_i = n)$

Problem

确定用红、白、蓝三色给$1 \times n$的棋盘的着色中,红格数是偶数,且至少有一个蓝格的着色方法数$h_n$
红:$\sum_{i = 0}^{\infty} \frac{1}{2i!} x^{2i}$
蓝:$\sum_{i = 1}^{\infty} \frac{1}{i!} x^{i}$
白:$\sum_{i = 0}^{\infty} \frac{1}{i!} x^{i}$
$h(x) = (\sum_{i = 0}^{\infty} \frac{1}{2i!}x^{2i}) (\sum_{i = 1}^{\infty} \frac{1}{i!} x^{i}) (\sum_{i = 0}^{\infty} \frac{1}{i!} x^{i})$
$h(x) = \frac{e^x + e^{-x}}{2}e^x(e^x - 1)$
$h(x) = \frac{e^{3x} - e^{2x} + e^x - 1}{2}$
$e^x = \sum_{i = 0}^{\infty} \frac{1}{i!} x^i$
$h(x) = -\frac{1}{2} + \sum_{i = 0}^{\infty}\frac{(3x)^i - (2x)^i + x^i}{2 * i!}$
$$h_n = \frac{3^n - 2^n + 1}{2}$$
BZOJ 3771 Triple
BZOJ 3456 城市规划
BZOJ 3059 COUNTARI

生成函数求数列通项

$h_n = 5h_{n - 1} - 6h_{n - 2}(n \geq 2) , h_0 = 1 , h_1 = 2$
将其用生成函数形式写出,$n$次项用$n - 1 , n - 2$次项代替,得
$h(x) = 5x(h(x) - h_0) - 6x^2h(x) +(h_0 - h_1x)$
将$h_0 , h_1$代入,$h(x)$移至一侧,得

$$ h(x) = \frac{1 - 7x}{6x^2 - 5x + 1} $$

将其化为$\frac{S}{1 - rx}$的形式,得

$$ h(x) = \frac{5}{1 - 2x} - \frac{4}{1 - 3x} $$

最后用形式幂级数表示

$$ h(x) = \sum_{i = 0}^{\infty}(5 * 2 ^ i - 4 * 3 ^ i) x ^ i $$

Last modification:November 7th, 2018 at 09:02 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment