多项式与生成函数
高数基础补档
复数相关
棣莫弗定理:\((cos\theta+i\sin\theta)^n=\cos(n\theta)+i\sin(n\theta)\).
欧拉公式:\(e^{i\pi}=-1\).
也就是\(e^{2i\pi}=1\),同时又有\(e^{i\theta}=cos\theta+i·sin\theta\),证明直接使用泰勒展开.
单位根:对于\(x^n=1\),我们会有\(n\)个根,设第\(k\)个根为\(\omega_n^k\).那么我们有:\(\omega_n^k=e^{2\pi\frac k ni}=cos(2\pi\frac kn)+i·sin(2\pi\frac kn)\).
单位根有以下性质:
- 折半引理:\(\omega_{2n}^{2k}=\omega_n^k\\\),由我们上面推导的通项公式即可证明.
- 消去引理:\(\omega_n^{k+\frac n 2}=-\omega_n^k\\\),同样使用通项，运用三角恒等变换可证明.
分圆多项式
上复平面,设\(S_k=(\cos\frac{2k\pi}{n},\sin\frac{2k\pi}{n})\),也就是\(z_k=\cos\frac{2k\pi}{n}+i\sin\frac{2k\pi}{n}\)是方程\(z^n-1=0\)的复根.我们把这个方程写开: \[ z^n-1=(z-1)(z^{n-1}+z^{n-2}+\cdots+1)=0 \] 不难发现\(z=1\)是平凡解.
我们不妨定义\(f(x)=\prod_{k=1}^n(1+X^k)=\sum_{k\geq 0}a_kX^k\),事实上我们有: \[ \frac{1}{n}\sum_{j=1}^nf(\omega_n^j)=\frac{1}{n}\sum_{j=1}^n\sum_{k\geq 0}a_k\omega^{kj}_n\\ =\frac{1}{n}\sum_{k\geq 0}a_k\sum_{j=1}^n\omega_{n}^{kj}\\ =\sum_{j\geq 0}a_{jn}+\frac{1}{n}\sum_{k\geq 0,n\nmid k}a_k\frac{1-\omega^{nj}_n}{1-\omega^{k}_n}\omega_{n}^j\\ =\sum_{j\geq 0}a_{jn} \] 事实上,我们令\(d=\frac{n}{\gcd(j,n)}\),容易发现\(f(\omega_n^j)=(\prod_{k=1}^d(1+\omega_n^{kj}))^{\frac{n}{d}}\),又容易发现\(n|jd\).
接下来观察\(X^d-1=\prod_{k=1}^d(X-\omega_{n}^{kj})\),带入\(X=-1\)得到\(f(\omega_n^j)=\begin{cases}2^{\frac{n}{d}}&d\in \text{odd}\\0&d\in\text{even}\end{cases}\).
接下来考虑拿到\(\sum_{j}a_{jn}\),只需求\(\frac{1}{n}\sum_{j=1}^nf(\omega_n^j)=\frac{1}{n}\sum _{d\in \text{odd},\gcd(j,n)=\frac{n}{d}}2^{\frac{n}{d}}=\frac{1}{n}\sum_{d\in\text{odd}}\varphi(d)2^{\frac{n}{d}}\).
Example(尺规做正n边形问题)
碰瓷高斯问题.
一步一步来.根据尺规作图理论:尺规作图只可以实现\(+,-,\times,\div,\sqrt[2]{}\)五种操作.而对于正\(n\)边形,显然只要我们能将\(\cos\frac{2\pi}{n}\)用只含上述五种操作和若干整数表示出来,那就一定可行.
正五边形问题
观察正五边形在复平面上的图像,注意到有两对点互为共轭复数,我们令: \[ \sigma_1=z_1+z_4\\ \sigma_2=z_2+z_3 \] 不难验证: \[ \sigma_1+\sigma_2=-1\\ \sigma_1\sigma_2=-1 \] 可以求出复合条件的解,将\(z\)带入又有: \[ \sigma_1=2\cos\frac{2\pi}{5}\\ \sigma_2=2\cos\frac{4\pi}{5} \] 于是我们显然可以求得.
正七边形
类似正五边形,最后会导出三次方程:根中含有三次根号,因此不行.
正n边形
要解决正17边形,只需要解决正n边形,然后令n=17即可.
你问我咋想到的下面的证明?问高斯去.
下面其实用到了ntt知识,但我懒得扔下面了.
先假设\(n\in prime\),我们用\(p\)代替\(n\).
我们有\(z_1=\cos\frac{2\pi}{p}+i\sin\frac{2\pi}{p}\),由于其它的\(z\)都可以表示成它的幂,因此我们记\(\varepsilon =z_1\).
我们现在想要这么分组: \[ \sigma_{k+1}=\sum_{1\leq l\leq p-1,f(l,k)=1}\varepsilon^l \]
泰勒展开
即\(f(x)=g(x)=f(x_0)+\sum_{k\geq 1}\frac{f^{(k)}(x_0)}{k!}(x-x_0)^k\\\).\(x_0=0\)的时候是麦克劳林级数.
麦克劳林展开是生成函数的基础,我们所谓的生成函数的封闭形式其实就是麦克劳林展开的逆运算(可能也不能完全等价,但笔者能力不够,暂且这么理解).
多项式
多项式基础
点值表示法和系数表示法
代数基本定理:一个\(n-1\)次方程在复数域上有且只有\(n-1\)个根.
定理:一个\(n-1\)次多项式在\(n\)个不同点的取值唯一确定了该多项式.
证明:考虑反证法,假设命题不成立,则存在两个\(n-1\)次多项式\(A(x)\)和\(B(x)\)且有\(\forall i\in[0,n-1],A(x_i)=B(x_i)\\\).
令\(C(x)=A(x)-B(x)\),那么\(C(x)\)至多是一个\(n-1\)次多项式且\(\forall i\in[0,n-1],C(x_i)=0\\\),也就是\(C(x)\)有\(n\)个根,与代数基本定理不符合.
由上面的内容,多项式有点值表示法和系数表示法两种:
系数表示法:\(A(x)=\sum_{i=0}^{n-1}a_ix^i\\\).
点值表示法:\(y_i=\sum_{j=0}^{n-1}a_jx_i^j\\\).
已知多项式点值表示法求系数表示法的过程被称为插值.
拉格朗日插值
构造多项式\(\sum_{i=0}^{n-1}y_i(\prod_{j=0\and j\ne i}^{n-1}\frac {x-x_j}{x_i-x_j})\\\).显然当\(x=x_i\)时,该多项式的答案为\(y_i\).
另外,如果\(x_i=i\),不难发现这个式子可以写成: \[ \sum_{i=1}^{n}y_i(\prod_{j=1\and j\ne i}^{n}\frac {x-x_j}{x_i-x_j})\\\\ =\sum_{i=1}^ny_i(\prod_{j=1\and j\ne i}^n\cfrac{x-j}{i-j})\\ =\sum_{i=1}^ny_i(-1)^{n-i}(\cfrac{1}{(i-1)!(n-i)!}\prod_{j=1,j\ne i}^{n}(x-j)) \]
多项式运算
考虑两个多项式相乘,如果我们已知他们的点值表示法,显然可以直接相乘.
这为我们提供了一种思路:先将系数表示法转化为点值表示法,进行相乘之后再转化回系数表示法.
这引出以FFT为代表的多项式乘法,并拓展到了多种多项式运算.
多项式乘法
快速傅里叶变换(FFT)
DFT
将\(n\)次单位根(默认\(n\)是二的整次幂,如果少了的话补零,设\(n=2^w\))分别带入\(A(x)\)得到点值向量\(A(\omega_n^k)\\\).
如果朴素带入,复杂度显然不可接受.
考虑: \[ A(x)=\sum_{i=0}^{n-1}a_ix^i\\=\sum_{i=2k,k\in\mathbb{N}}^{n-2}a_ix^i+\sum_{i=2k+1,k\in\mathbb{N}}^{n-1}a_ix^i\\ =\sum_{i=2k,k\in\mathbb{N}}^{n-2}a_ix^{2k}+x\sum_{i=2k+1,k\in\mathbb{N}}^{n-1}a_ix^{2k}\\ \] 令\(A_1(x)=\sum_{i=2k,k\in\mathbb{N}}^{n-2}a_ix^{k}, A_2(x)=\sum_{i=2k+1,k\in\mathbb{N}}^{n-1}a_ix^{k}\\\),那么\(A(x)=A_1(x^2)+xA_2(x^2)\\\).
接下来分类讨论:
\(\forall 0\leq k\leq \frac n 2-1,k\in\mathbb{N}\\\),我们有: \[ A(\omega_n^k)=A_1(\omega_n^{2k})+\omega_n^kA_2(\omega_n^{2k})\\ \] 根据折半引理: \[ A(\omega_n^k)=A_1(\omega_{\frac n 2}^k)+\omega_n^kA_2(\omega^k_{\frac n 2})\\ \] 这样我们处理完了前半部分.
\(\forall \frac n 2\leq k+\frac n 2\leq n-1,k\in\mathbb{N}\\\),我们有: \[ A(\omega_n^{k+\frac n 2})=A_1(\omega_n^{2k+n})+\omega_n^{k+\frac n 2}A_2(\omega_n^{2k+n})\\ \] 根据消去引理: \[ A(\omega_n^{k+\frac n 2})=A_1(\omega_{\frac n 2}^k)-\omega_n^kA_2(\omega_{\frac n 2}^k)\\ \] 综上,我们可以递归处理\(A_1\)和\(A_2\),然后合并得到\(A\)的答案,可以分治.
######IDFT
设\(A(\omega_n^k)=d_k\\\),构造多项式\(F(x)=\sum_{i=0}^{n-1}d_ix^i\\\).
我们求出\(F(x)\)的点值表示,设\(c_k=F(\omega_n^{-k})\\\),也即: \[ c_k=\sum_{i=0}^{n-1}d_i(\omega_n^{-k})^i\\=\sum_{i=0}^{n-1}(\sum_{j=0}^{n-1}a_j(\omega_n^i)^j)(\omega_n^{-k})^i\\ =\sum_{j=0}^{n-1}a_j\sum_{i=0}^{n-1}(\omega_n^i)^{j-k}\\ \] 当\(j=k\)时,显然\(\sum_{i=0}^{n-1}(\omega_n^i)^{j-k}=n\\\).
否则根据等比数列求和公式,\(\sum_{i=0}^{n-1}(\omega_n^i)^{j-k}=\frac{\omega^0_n[(\omega_n^{j-k})^n-1]}{\omega_n^{j-k}-1}=0\\\).
所以\(\sum_{i=0}^{n-1}(\omega_n^i)^{j-k}=n[j=k]\\\).
那么我们有\(c_k=na_k, a_k=\frac{c_k}{n}\\\).
######写法
递归写法显然.
递归过程中,第\(k\)层相当于在根据数在第\(k\)位的二进制数是\(1\)还是\(0\)来分类.那显然可以求出最后一层的数组,然后向上合并.
(没找到fft的代码,懒得写了,直接用的ntt的,注意快速幂要处理幂为负数的情况).
1 | inline void init_rev(int limit,int k){ |
#####快速数论变换(NTT)
由于FFT中的单位根会产生精度误差,因此在膜\(998244353\)意义下,通常会选择NTT来进行多项式乘法.
NTT与FFT的运算过程基本相同,证明过程基本相同,唯一不同的是将单位根改为了原根.
根据上面FFT的证明过程,我们知道,设原根为\(g\),\(g_n=g^{\frac {p-1}n}\\\),只需要证明原根满足以下条件,就可以进行变换:
- \(g_n^n=g_n^0=1\)且\(\forall 0\leq i<j<n,g_n^i\ne g_n^j\),证明由原根的性质.
- 折半引理:\(g_{2n}^{2k}=g_{n}^k\),证明显然.
- 消去引理:\(g_{n}^{k+\frac n 2}=-g^k_n\\\).由于\(g^{\frac {p-1}2}=-1\),该结论显然成立.
由上我们证明了,我们完全可以使用\(g_n\)代替\(\omega_n\)进行变换.
另外,注意到\(998244352=2^{23}\times 7\times 17\\\),而\(2^{23}\approx 8\times 10^6\\\).因而,当\(n\leq 8\times 10^6\)的时候,\(g_n\)可以直接求出.这也是为什么大部分NTT题目都使用\(998244353\)作为模数的原因.
范德蒙德矩阵理解
范德蒙德矩阵形如: \[ \begin{bmatrix}1&\alpha_1&\cdots&\alpha_1^{n-1}\\1&\alpha_2&\cdots&\alpha_2^{n-1}\\\vdots&\vdots&\ddots&\vdots\\1&\alpha_m&\cdots&\alpha_m^{n-1}\end{bmatrix}\in\mathbb{R}^{m\times n} \] 如果取单位根,我们有: \[ \begin{bmatrix}1&1&\cdots&1\\1&\omega_n^1&\cdots&\omega_2^{n-1}\\\vdots&\vdots&\ddots&\vdots\\1&\omega_n^{n-1}&\cdots&\omega_n^{(n-1)^2}\end{bmatrix}\in\mathbb{R}^{n\times n} \] 这就是我们在做FFT(一个线性变换)的时候的变换矩阵.所以我们有: \[ \begin{bmatrix}1&1&\cdots&1\\1&\omega_n^1&\cdots&\omega_2^{n-1}\\\vdots&\vdots&\ddots&\vdots\\1&\omega_n^{n-1}&\cdots&\omega_n^{(n-1)^2}\end{bmatrix}^{-1}=\frac{1}{n}\begin{bmatrix}1&1&\cdots&1\\1&\omega_n^{-1}&\cdots&\omega_2^{-(n-1)}\\\vdots&\vdots&\ddots&\vdots\\1&\omega_n^{-(n-1)}&\cdots&\omega_n^{-(n-1)^2}\end{bmatrix} \]
分治FFT
给定\(g(x)\)和\(f(0)\),求\(f(x)=\sum_{y=1}^xf(x-y)g(y)\),答案对\(998244353\)取膜.
考虑分治,假如我们已经知道了\(f(x),x\in[1,\frac n 2]\).那我们可以计算出这段部分对\(f(y)，y\in[\frac n 2+1,n]\)的贡献.
这显然是一个卷积的形式,我们直接计算\(f\)和\(g\)的乘积并贡献上去.
####多项式求逆
对于多项式\(P(x)\),找到\(Q(x)\)使得\(Q(x)P(x)\equiv 1\pmod {x^{n}}\\\).显然\(Q(x)\)是唯一的.
首先不妨设\(n=2^k\\\).
如果我们已知\(P(x)Q_{k-1}(x)\equiv 1\pmod {x^{2^{k-1}}}\\\),同时肯定有\(P(x)Q_{k}(x)\equiv 1\pmod {x^{2^{k-1}}}\\\),相减得到\(Q_k(x)-Q_{k-1}(x)\equiv 0\pmod {x^{2^{k-1}}}\\\).
两边平方: \[ Q_k^2(x)+Q^2_{k-1}(x)-2Q_k(x)Q_{k-1}(x)\equiv 0\pmod {x^{2^k}}\\ \] 两边乘一下\(P(x)\): \[ Q_k(x)-2Q_{k-1}(x)+P(x)Q_{k-1}^2(x)\equiv 0\pmod {x^n}\\ Q_k(x)\equiv 2Q_{k-1}(x)-P(x)Q_{k-1}^2(x)\pmod {x^n}\\ \] 根据主定理，这么做复杂度是\(O(n\log_2n)\)的.
同时,多项式求逆可以解决上面提到的分治FFT.我们注意到分治FFT的条件等价于: \[ F(x)\equiv F(x)G(x)+f_0\pmod {x^{n+1}}\\ F(x)=\frac{f(0)}{1-G(x)}\pmod {x^{n+1}} \] 于是可以直接做多项式求逆.
多项式除法
对于\(n\)次多项式\(F(x)\)和\(m\)次多项式\(G(x)\),找到\(Q(x),R(x)\)使得\(F(x)=G(x)Q(x)+R(x)\\\).
考虑对于\(n\)次多项式\(F(x)\),令\(F_R(x)=x^n F(\cfrac{1}{x})\),如果设\(f_i\)为其\(x^i\)项前的系数,不难发现\(f_R(i)=f(n-i)\).
那么我们有: \[ F(x)=G(x)Q(x)+R(x)\\ F(\cfrac{1}{x})=G(\cfrac{1}{x})Q(\cfrac{1}{x})+R(\cfrac{1}x)\\ x^nF(\cfrac{1}{x})=x^mG(\cfrac{1}{x})x^{n-m}Q(\cfrac{1}{x})+x^{n-m+1}x^{m-1}R(\cfrac{1}{x})\\ F_R(x)=G_R(x)Q_R(x)+x^{n-m+1}R_R(x)\\ F_R(x)\equiv G_R(x)Q_R(x)\pmod {x^{n-m+1}}\\ Q_R(x)\equiv F_R(x)G_R^{-1}(x)\pmod {x^{n-m+1}} \] 于是只要做一遍多项式求逆即可求得\(Q(x)\),再做一遍相减既可以得到\(R(x)\).
多项式ln
给出\(n-1\)次多项式\(A(x)\),求一个多项式\(B(x)\),满足\(B(x)\equiv \ln A(x)\).
我们有: \[ B(x)\equiv \ln A(x)\pmod {x^n}\\ B'(x)\equiv \cfrac{A'(x)}{A(x)}\pmod {nx^{n-1}}\\ B(x)\equiv \int \cfrac{A'(x)}{A(x)}dx\pmod {x^n}\\ \]
另外,考虑中间求导的过程中,其实模数也要相应发生变化,但是由于模数是从更高次变低,而最后积分的时候又要变回来,所以可以直接忽略变化.
定理:在模意义下当且仅当\([x^0]f(x)=1\)的时候,\(f(x)\)有对数多项式.
我们对最后再做一步: \[ B(x)\equiv \int_0^x \cfrac{A'(t)}{A(t)}dt+B(0)\pmod {x^n}\\ \] 首先\(B(0)=\ln A(0)=\ln a_0\),如果\(a_0\in\mathbb{Q}\and a_0\ne 1\),则\(B(0)\notin \mathbb{Q}\),因此不能放到模意义下,自然不存在对数多项式.
若\([x^0]f(x)=1\)的时候,\(B(0)=0\),因此可以直接求出答案.
牛顿迭代
给定多项式\(G(x)\),求一个多项式\(F(x)\)满足\(G(F(x))\equiv 0\pmod {x^n}\).
首先\(n=1\)的时候,也就是求\(G(F(x))\equiv 0\pmod x\).这个要根据具体题目具体分析求出.
假设我们已经求出了在\(\bmod x^{\lceil\frac{n}{2}\rceil}\)意义下的答案\(F_0(x)\),我们考虑在\(F_0(x)\)处做泰勒展开: \[ G(F(x))=\sum_{k=0}^{+\infty}\frac{G^{(k)}(F_0(x))}{k!}(F(x)-F_0(x))^k\equiv 0\pmod{x^n}\\ \] 考虑\(F(x)-F_0(x)\),由于\(F_0(x)\equiv F(x)\pmod{x^{\lceil\frac{n}{2}\rceil}}\),因此,因此\((F(x)-F_0(x))^2\equiv 0\pmod{x^n}\).
于是我们有: \[ \sum_{k=0}^{+\infty}\frac{G^{(k)}(F_0(x))}{k!}(F(x)-F_0(x))^k\equiv 0\pmod{x^n}\\ G(F_0(x))+G'(F_0(x))(F(x)-F_0(x))\equiv 0\pmod{x^n}\\ F(x)\equiv F_0(x)-\frac{G(F_0(x))}{G'(F_0(x))}\pmod{x^n} \] 牛顿迭代可以用来证明多项式求逆的式子同样正确.
多项式开方
给定\(h(x)\),设\(g(f(x))=f^2(x)-h(x)\),求零点.
根据牛顿迭代,有: \[ f(x)\equiv f_0(x)-\frac{f^2(x)-h(x)}{2f_0(x)}\equiv \frac{f^2(x)+h(x)}{2f_0(x)}\pmod{x^n} \] 还没完,用牛顿迭代前一定要求\(g(a)\equiv 0\pmod {x^n}\)的解,也就是\([x^0]h(x)\)的开根,用二次剩余算.
多项式exp
给定\(h(x)\),设\(g(f(x))=\ln f(x)-h(x)\),求零点.
根据牛顿迭代,有: \[ f(x)\equiv f_0(x)-\frac{\ln f_0(x)-h(x)}{\frac{1}{f_0(x)}}\pmod{x^n}\\ \equiv f_0(x)(1-\ln f_0(x)+h(x))\pmod{x^n} \] 还没完,还需要求\(g(a)\equiv 0\pmod {x^n}\)的解,注意到存在\(\exp\)当且仅当\([x^0]g(x)\equiv 0\),此时\(f(x)\equiv 1\pmod{x}\).
多项式快速幂
求\(\ln\)后求\(\exp\)即可,唯一的问题是为什么指数可以对\(p\)取膜.
我们有一个结论: \[ f(x^p)\equiv f(x)^p\pmod p \] 这个结论很简单,注意到\((a+b)^p\equiv a^p+b^p\pmod p\)即可.
而又由于\(n<p\),因此\(f(x)^p\equiv f(0)\pmod p\),通常取\(f(0)=1\),于是就可以直接对\(p\)取膜.
多项式运算全家桶(重载运算符版)
我们必须指出的一点是,虽然重载运算符很好看,但是大部分情况下还是需要指针传参.例如在这里,由于做\(\exp\)的时候的直接数组传参,会导致\(\exp\)的复杂度退化到\(O(n\log^2n)\).
1 |
|
集合幂级数
集合幂级数形如\(\sum_{i=0}^{2^n-1}a_ix^i\),其中二进制数\(i\)表示\(\{1,2,...,n\}\)的一个子集,用\(|i|\)表示该子集大小,等价于对二进制使用的popcount函数.
下述级数如无特别说明均为集合幂级数.
与/或卷积
高维前缀和:\(c_i=\sum_{j\subseteq i}a_j\\\).
高维后缀和:\(c_i=\sum_{j\supseteq i}a_j\\\).
上述过程又称快速莫比乌斯变换(FMT).
1 | for(int i=0;i<n;i++) |
或卷积:\(c_i=\sum_{j}\sum_{k}[j \or k=i]a_jb_k\\\).
与卷积:\(c_i=\sum_{j}\sum_{k}[j\and k=i]a_jb_k\\\).
二者求法类似,考虑如何求\(a\)和\(b\)的或卷积:
引理:
若\(j,k\subseteq i\),则\(j\or k\subseteq i\),逆命题同样成立.
若\(j,k\supseteq i\),则\(j\and k\supseteq i\),逆命题同样成立.
设\(a,b,c\)的高维前缀和分别为\(A,B,C\),我们有: \[ A_iB_i=(\sum_{j\subseteq i}a_j)(\sum_{k\subseteq i}b_k)\\=\sum_{j,k\subseteq i}a_ib_k\\=\sum_{k\or j\subseteq i}a_ib_k\\=C_i\\ \] 现在考虑已知\(C\)求\(c\),本质上是一个反演.注意到\(\sum_{r\subseteq p}(-1)^{|r|}=\sum_{k=0}^{|p|}C_{|p|}^k(-1)^k=[p=0]\\\),我们有: \[ c(p)=\sum_{q\subseteq p}[p-q=0]c(q)\\=\sum_{q\subseteq p}\sum_{r\subseteq (p-q)}(-1)^{|r|}c(q)\\ =\sum_{r\subseteq p}(-1)^{|r|}\sum_{q\subseteq (p-r)}c(q)\\=\sum_{r\subseteq p}(-1)^{r}C(p-r)\\=\sum_{r\subseteq p}(-1)^{|p|-|r|}C(r)\\ \] 于是有\(c(S)=\sum_{T\subseteq S}(-1)^{|S|-|T|}C(T)\\\)(实际上就是个差分的过程).
因而做两遍高维前缀和再反推回去即可,复杂度\(O(2^nn)\).
与卷积即改为高维后缀和.
1 | inline void FWT_and(ll *a,ll t,int limit){//FWT:t=1;IFWT:t=-1 |
异或卷积
异或卷积:\(c_i=\sum_j\sum_k[j\oplus k=i]a_jb_k\\\).
引理:\((i\oplus j)\and k=(i\and k)\oplus (j\and k)\).
证明的话考虑如果\(k=0\),二者显然相等;当\(k=1\)的时候,左右都等价于\((i\oplus j)\).
快速沃尔什变换(FWT):
定义集合幂级数\(FWT(a)\),满足\(FWT(a)_i=\sum_{j=0}^{2^n-1}(-1)^{|i\and j|}a_j\\\).
那么有: \[ FWT(c)_i=\sum_{j=0}^{2^n-1}(-1)^{|i\and j|}c_j\\=\sum_{j=0}^{2^n-1}(-1)^{|i\and j|}\sum_{k=0}^{2^n-1}\sum_{l=0}^{2^n-1}[k\oplus l=j]a_kb_l\\ =\sum_{k=0}^{2^n-1}\sum_{l=0}^{2^n-1}(-1)^{|(k\oplus l)\and i|}a_kb_l\\=\sum_{k=0}^{2^n-1}\sum_{l=0}^{2^n-1}(-1)^{|k\and i|}a_k(-1)^{|l\and i|}b_l\\ =FWT(a)_iFWT(b)_i\\ \] 时间复杂度\(O(2^nn)\).
逆运算的话考虑实现过程,反向就行.不过可以把过程中乘上的\(\frac{1}2\)都提出来乘到最后.
FMT可以看作是FWT在解决与/或卷积时的特例.
1 | inline void FWT_xor(ll *a,ll t,int limit){//FWT:t=1;IFWT:t=-1 |
快速沃尔什变换
线性代数角度
我们来重定义一下所谓的FWT.
首先类比FFT,我们希望存在一个线性变换\(FWT\),使得
- 若\(c_i=\sum_{j\oplus k}a_jb_k\),则\(FWT(c)=FWT(a)FWT(b)\).
- 这个线性变换是可逆的.
- 做这个线性变换和其逆变换的复杂度都可以接受.
我们设\(FWT(A)_i=\sum_{j}w(i,j)A_j\),我们想要做的就是构造一组满足上述条件的\(w\).
考虑: \[ FWT(C)_i=FWT(A)_iFWT(B)_i\\ \sum_{j}w(i,j)C_j=\sum_{j,k}w(i,j)w(i,k)A_jB_k \] 再考虑: \[ C=A*B\\ C_i=\sum_{k\oplus l=i}A_kB_l\\ \sum_{j}w(i,j)C_j=\sum_jw(i,j)\sum_{k\oplus l=j}A_kB_l\\ \sum_{j,k}w(i,j)w(i,k)A_jB_k=\sum_jw(i,j)\sum_{k\oplus l=j}A_kB_l\\ \sum_{j,k}w(i,j)w(i,k)A_jB_k=\sum_{j,k}A_jB_kw(i,j\oplus k) \] 比较两边系数,有\(w(i,j)w(i,k)=w(i,j\oplus k)\).只要满足这个条件,我们就能构造出一组满足条件(1)的线性变换.如果这个线性变换对应的矩阵可逆,那么就满足了条件(2).
而由于\(\oplus\)是集合的运算,我们可以对二进制分开考虑.换句话说,如果\(a=\sum_{i=0}a_i2^i,b=\sum_{i=0}b_i2^i\),那么\(w(a,b)=\prod_{i=0}w(a_i,b_i)\)一定是满足条件的.
这样我们就可以只求一个\(2\times 2\)的线性变换矩阵就好.我们接下来将对三种常见的基础位运算(\(\or,\and,xor(\oplus)\))分别讨论这个矩阵.我们先来解决第三个问题:如何快速求出\(FWT(a)\)呢?
考虑和FFT一样折半,令\(i_0\)为\(i\)的最高位是否是\(1\),\(i'\)为\(i\)去掉最高位后的二进制数字,令\(n=2^m\)我们有: \[ FWT(A)_i=\sum_{j=0}^{2^m-1}w(i,j)A_j\\ =\sum_{j=0}^{2^{m-1}-1}w(i,j)A_j+\sum_{j=2^{m-1}}^{2^m-1}w(i,j)A_j\\ =w(i_0,0)\sum_{j=0}^{2^{m-1}-1}w(i',j')A_j+w(i_0,1)\sum_{j=2^{m-1}}^{2^m-1}w(i',j')A_j \] 这样就实现了规模减半,复杂度\(O(mn)\).
下面我们设FWT的变换矩阵为\(\begin{bmatrix}w(0,0)&w(0,1)\\w(1,0)&w(1,1)\end{bmatrix}\).顺便一提,不难发现,最后对整体做的矩阵是这个矩阵的克罗内多积.
或卷积
取矩阵\(\begin{bmatrix}1&0\\1&1\end{bmatrix}\).其逆矩阵为\(\begin{bmatrix}1&0\\-1&1\end{bmatrix}\).
与卷积
取矩阵\(\begin{bmatrix}1&1\\0&1\end{bmatrix}\).其逆矩阵为\(\begin{bmatrix}1&-1\\0&1\end{bmatrix}\).
异或卷积
取矩阵\(\begin{bmatrix}1&1\\1&-1\end{bmatrix}\).其逆矩阵为\(\begin{bmatrix}\frac{1}2&\frac12\\\frac12&-\frac12\end{bmatrix}\).
生成函数角度
我们再从生成函数角度理解一下FWT.
我们重新定义幂乘法:\(x^Sx^T=x^{S\oplus T}\),显然幂乘法该满足的性质它都满足.
观察FWT的式子: \[ FWT(A)_S=\sum_{T=0}^{2^n-1}(-1)^{|S\and T|}a_T\\ IFWT(A)_S=\frac{1}{2^n}FWT(A)_S \] 这等价于: \[ [x^S]FWT(A)=\sum_{T=0}^{2^n-1}(-1)^{|S\and T|}a_T\\ [x^S]IFWT(A)=[x^S]\frac{1}{2^n}FWT(A) \]
子集卷积
子集卷积:\(c_i=\sum_{j}\sum_{k}[j\and k=\empty,j\or k=i]a_jb_k\\\).
意识到该卷积与或卷积的差别在于:或卷积会多累加一些\([j\and k\ne \empty]\)的答案,而\([j\and k=\phi,j\or k=i]=[|j|+|k|=|i|,j\or k=i]\\\).
因而可以将原集合按照元素个数分组做FMT,然后再\(n^2\)次结合,并做IFMT,最终将结果累计,复杂度\(O(2^nn^2)\).
集合占位幂级数
其实就是设\(g_{i,j}=z^if_j\),然后做卷积(类似子集卷积).
Example
Example1([AGC034F] RNG and XOR)
设\(f_i(n)\)表示操作\(n\)次后第一次变成\(i\)的概率,\(g_i(n)\)表示操作\(n\)次后变成\(i\)的概率.\(F,G\)分别是其生成函数.
注意到\(G_i=F_iG_0,F_i=\frac{G_i}{G_0}\),而\(F_i'(1)\)就是期望.接下来的问题在于如何求\(G\).
接下来涉及到的东西就很本质了,我们一开始先把\(a_i\rightarrow \frac{a_i}{\sum
a}\),然后做\(A=FWT(a)\),注意这里\(A_0=\sum a=1\),FWT自身有很好的性质:\(a=\frac{1}{2^N}FWT(A)\).我们做\(n\)次操作后得到的概率数组也就是\(\frac{1}{2^N}FWT(A^n)\).展开FWT的式子,自然有:
\[
g_i(n)=\sum_{j=0}^{2^N-1}(-1)^{|i\and j|}A_j^nx^n\\
G_i=\sum_{j=0}^{2^N-1}(-1)^{|i\and j|}\frac{1}{1-A_jx}\\
F_i=\frac{G_i}{G_0}\\
F_i'=\frac{G_i'G_0-G_0'G_i}{G_0^2}\\
=\frac{(\sum_{j=0}^{2^N-1}(-1)^{|i\and
j|}\frac{A_j}{(1-A_jx)^2})(\sum_{j=0}^{2^N-1}\frac{1}{1-A_jx})-(\sum_{j=0}^{2^N-1}\frac{A_j}{(1-A_jx)^2})(\sum_{j=0}^{2^N-1}(-1)^{|i\and
j|}\frac{1}{1-A_jx})}{(\sum_{j=0}^{2^N-1}\frac{1}{1-A_jx})^2}
\] (我草这个式子太顶级了)
但是我们冷静一下,这个题与普通生成函数不同的地方在于,我们要求\(F'_i(1)\),因此我们直接把\(x=1\)带入算一算就好.不过由于\(A_0=1\),我们必须要解决分母为\(0\)的情况,解决的方法是分母乘上\((1-x)\),这样就消掉了\(j=0\)的项,同时分子由于是减法可以抵消一下.
然后大概做做吧,感觉太顶级了.
Example2([QOJ5089]环覆盖)
合法显然当且仅当每个点度数为偶数,考虑直接拿一个二进制数将每个点度数奇偶性压起来,如果选中一条边\(u\leftrightarrow v\)就异或上\((2^u+2^v)\).最后要求这个二进制数是\(0\).我们用一个二元组\((a,F)\)表示在集合幂级数上异或上\(a\),在多项式上乘上\(F\).显然一条边是\((0,1)+(2^u+2^v,x)\).注意到这是可以定义乘法运算和标量乘法运算的,也就能做FWT,而且在做FWT的时候要么乘上\(1+x\)要么乘上\(1-x\),做完FWT得到的每一个\(FWT_i\)一定形如\((1+x)^k(1-x)^{m-k}\),做IFWT的时候直接求\(\frac{1}{2^N}\sum (1+x)^k(1-x)^{m-k}\)即可.
仔细想想这个过程:有一句名言是只要看到生成函数就一定存在分配律,这里也是一样的,由于存在一种选择:选不选这条边,因此这里也就有了两种情况:\((0,1)\)和\((2^u+2^v,x)\),分开两种情况就实现了FWT.
问题在于对于每个\(i\)求\(k\),也就是对于每个\(i\)求有多少条边满足\(|i\and(2^u+2^v)|=1\),也就是求有多少条边一段链接在了\(i\)的内部,另一端连接在了外部,这个补集转化一下,做高维前缀和.
Example3(CF1034E Little C Loves 3 III)
仍然是子集卷积,转化为\(c_i=\sum_{j}\sum_{k}[|j|+|k|=|i|,j\or k=i]a_jb_k\\\).然后我们将\(a_j\)乘上\(4^j\),将\(b_k\)乘上\(4^k\),最后把\(c_i\)除去\(4^i\)对\(4\)取膜就行.
还有个用到FWT的本质的矩阵做法,大概是手推矩阵然后再手推求逆.
Example4(CF1336E2 Chiori and Doll Picking)
先考虑easy version.首先求出线性基,如果线性基的大小\(k\)比较小,我们可以直接\(2^k\)枚举一下.而如果线性基较大,我们先消成最简线性基,然后主元位置有多少个\(1\)取决于选了多少个元素,其他位置共有\(m-k\)个,可以直接状压进状态.这样复杂度就是\(O(\min\{2^k,m^22^{m-k}\})\).
那么我们怎么优化呢?首先\(k\)较大的时候有点难做,我们看看能不能优化到\(2^{m-k}\).
考虑设\(f_i^c=[|i|=c]\),将线性基能做出的线性空间设为\(A\),\(A_S=1\)当且仅当线性基能异或出\(S\)(最后再把那些废元素贡献到答案里).那么\(popcount=c\)的答案就是\(IFWT(FWT(F)FWT(A))_0\).考虑\(IFWT_0=\frac{1}{2^m}\sum_{i=0}^{2^m-1}FWT(F)_iFWT(A)_i\),问题在于这个东西好像也不好做.
然后接下来开始一波顶级操作(下面的操作全部基于行向量+行操作):
引理1:\(FWT(A)\)要么是\(2^k\),要么是\(0\).
考虑: \[ A* A=A\times 2^k \] 这句是为啥呢?因为对于右边的每一个数字\(x\)和左边的一个数字\(y\),如果它们都在线性基中,一定存在一个数字\(z\)满足\(y\oplus z=x\),不然就是\(0\).
于是我们有: \[ FWT(A)_i\cdot FWT(A)_i=FWT(A)_i\times 2^k\\ FWT(A)_i=0\or2^k \] 引理2:\(FWT(A)_i=2^k\Leftrightarrow \forall x,A_x\ne 0,|i\and x|\equiv 0\pmod 2\).
直接展开上面的式子,用\(\sum_{S\subseteq T}(-1)^{|S|}=[T=\empty]\).
引理3:\(FWT(A)\)中值为\(2^k\)的位置构成一个线性基.
只需要证明封闭性就好,注意到如果\(i\)满足条件,\(j\)满足条件,一开始做FWT时我们已经注意到:\((i\oplus j)\and x=(i\and x)\oplus (j\and x)\).于是这个引理也显然成立.
引理4:\(FWT(A)\)中值为\(2^k\)的位置构成的线性基的大小是\(m-k\).
设这些位置构成的空间是\(B\),\(B_S=1\)当且仅当\(S\)在这个空间中.我们有: \[ FWT(A)=B\times 2^k\\ A=IFWT(B)\times 2^k \] 注意到\(a_0=1\),也就是\(\frac{2^k}{2^m}\sum b=1,\sum b=2^{m-k}\),这就证明了引理.
引理5:将\(A\)的线性基对应的矩阵从前往后消成最简,\(B\)的线性基对应的矩阵从后往前消成最简,上\(A\)下\(B\)拼成一个\(m\times m\)的矩阵,那么这个矩阵关于主对角线对称.
首先根据\(rank(A)+rank(B)=k+m-k=m\)可以知道主对角线一定全是\(1\),然后我们任取\(A\)中的一个基\(x\)和\(B\)中的一个基\(y\),应该有\(|x\and y|\equiv 0\pmod 2\).不难发现此时必定对称(画个图,不对称的话考虑主元对他俩的贡献就不是偶数了).
通过这个引理可以由\(A\)得知\(B\)长什么样.
引理6:\(FWT(F^c)_i\)只和\(|i|\)有关.
因为\(F^c_i\)只和\(|i|\)有关,这里考虑一下对称性就可以.因此设\(w_{d}^c=FWT(F^c)_i,|i|=d\).
然后注意到\(w_d^c=\sum_{i=0}^{2^m-1}(-1)^{|i\and (2^d-1)|}[|i|=c]\).组合意义展开一下: \[ w_d^c=\sum_{j=0}^{d}(-1)^{j}\binom{d}{j}\binom{m-d}{c-j} \] 接下来怎么做呢?令\(g_d=\sum_{i=0}^{2^m-1}[A_i=1][|i|=d]\),这里可以\(O(2^{m-k})\),然后乘起来就行了.
太顶级了吧.
Example5(CF 1326F2)
首先发现”如果没有边那么是\(0\)“这个限制太强了,如果我们能改为”如果是\(0\),那么可有边可无边”的话,整个序列就会被\(1\)的段分成若干两两无关的链.显然这是一步或卷积,这样我们就只需要求后者.如果设\(g_{len,S}\)表示长度为\(len\),一段长度为\(len-1\)的连续的\(1\)对应的集合是\(S\)的方案数,不难发现我们最后只需要做一个类似子集卷积的东西就行(前面的每个段会自动在后面放个\(0\)).
但是还没完,题目让我们求每一个,我们不难发现我们这样划分之后答案只取决于链的长度的可重集合,而本质不同的集合的数量很少,直接枚举就行.
Example6(qoj5019)
首先可以类似数位dp设计一个\(dp_{i,S}\)表示目前dp到了第\(i\)位,然后前面的\(limit\)是\(S\).接下来分类讨论当前的最大值限制是\(1\)还是\(0\).
这个题知道题解其实没什么难的,但是这个题告诉了我们:FWT作为一种线性变换,它是可以和其它线性变换一起做的,也就是说你是可以将其中的若干位做FWT,剩下若干位做其它的东西的.
生成函数
普通生成函数(OGF)
概念
我们定义一个幂级数形如\(A(z)=\sum_{k\geq 0}a_kz^k\),并使\([z^n]A(z)=a_n\).则称\(A(z)\)是\(\langle a_0,a_1,...\rangle\)的生成函数.
运算
- \(\alpha A(z)+\beta B(z)=\sum_{n\geq 0}(\alpha f_n+\beta g_n)z^n\).
- \(z^mA(z)=\sum_{n\geq 0}g_{n}z^{n+m}=\sum_{n\geq m}g_{n-m}z^n\).
- \(A(cz)=\sum_{n\geq 0}c^nf_nz^n\).
- \(A'(z)=\sum_{n\geq 1}ig_iz^{i-1}\).
- \(\int A(z)dz=\sum_{n\geq 0}\cfrac{1}{n+1}g_nz^{n+1}\).
- \(A(z)B(z)=\sum_{n\geq 0}(\sum_{k=0}^nf_kg_{n-k})z^n\).
- \(\cfrac{1}{1-z}A(z)=\sum_{n\geq 0}(\sum_{k=0}^ng_k)z^n\).
常见序列生成函数
- \(\cfrac{1}{1-z}=\sum_{k\geq 0}z^k\\\),\(\cfrac{1}{1-cz}=\sum_{k\geq 0}c^kz^k\\\).
证明显然.
- \((1+z)^r=\sum_{k\geq 0}\binom{r}{k}z^k\\\),\((1-z)^r=\sum_{k\geq 0}(-1)^k\binom{r}{k}z^k\\\).
证明根据二项式定理.
- \(\cfrac{1}{1-z^m}=\sum_{n\geq 0}[n|m]z^n\\\).
证明显然.
- \(\cfrac{1}{(1-z)^{n+1}}=\sum_{k\geq 0}\binom{n+k}{n}z^k,n\in\mathbb{N}\\\),\(\cfrac{z^n}{(1-z)^{n+1}}=\sum_{k\geq 0}\binom{k}{n}z^k,n\in\mathbb{N}\\\)
直接使用二项式定理展开\((1-z)^{-n-1}\),可以得到: \[ (1-z)^{-n-1}=\sum_{k\geq 0}(-1)^k\binom{-n-1}{k}z^k \] 反转上指标并使用对称恒等式得到上式.此外上式还有两个特殊形式: \[ \cfrac{1}{(1-z)^2}=\sum_{n\geq 0}(n+1)z^n\\\cfrac{z}{(1-z)^2}=\sum_{n\geq 0}nz^n \]
根据\((1)\)求导即可得到此式.
- \(e^z=\sum_{k\geq 0}\cfrac{z^k}{k!}\\\).
- \(\ln(\cfrac{1}{1-z})=\sum_{n\geq 1}\cfrac{1}{n}z^n\).
- \(\ln(1+z)=\sum_{k\geq 0}(-1)^k\cfrac{z^{k+1}}{k+1}\\\).
可以使用积分或泰勒展开证明.
- \(\frac{1-\sqrt {1-4x}}{2x}=\sum_{k\geq 0}\frac{\binom{2k}{k}}{k+1}x^k\).
也即卡特兰数\(C_k\)的生成函数,证明考虑: \[ xC^2+1=C \] 然后得到两个根,带入\(x=0\)舍掉一个.
指数生成函数(EGF)
https://zhuanlan.zhihu.com/p/53079223
序列\(\{a\}\)的指数生成函数定义为形式幂级数\(\hat F(x)=\sum a_n\frac{x^n}{n!}\).注意\([x^n]\hat F(x)=a_n\).
基本运算
我们有: \[ \hat F(x)\hat G(x)=\sum_{j\geq 0}a_j\frac{x^j}{j!}\sum_{k\geq 0}b_k\frac{x^k}{k!}\\ =\sum_{k\geq 0}x^k\sum_{j=0}^ka_jb_{k-j}\frac{k!}{j!(k-j)!}\frac{1}{k!}\\ =\sum_{k\geq 0}\frac{x^k}{k!}\sum_{j=0}^ka_jb_{k-j}\binom{k}{j} \] 即\(\lang\sum_{i=0}^n\binom{n}{i}a_ib_{n-i}\rang\)的EFG.
注意到有一个特例是\(x\hat F(x)\)就是\(\lang\binom{n}{n-1}a_i\rang\)的EGF.
封闭式
- \(e^x=\sum_{k\geq 0}\frac{x^k}{k!}\)
直接泰勒展开就可以得到
- \(e^{px}=\sum_{k\geq 0}p^k\frac{x^k}{k!}\)
换元后可以得到.一个经典特例是\(e^{-x}=\sum_{k\geq 0}(-1)^k\frac{x^k}{k!}\).
- \(\frac{e^x+e^{-x}}{2}=\sum_{k\geq 0}[2|k]\frac{x^k}{k!}\).
显然.
- \((1+x)^n=\sum_{k\geq 0}n^{\underline{k}}\frac{x^k}{k!}\).
做二项式定理就显然了.
- \(\ln(1+x)=\sum_{k\geq 1}(-1)^{k-1}(k-1)!\frac{x^k}{k!}\).
- \(\ln(1-x)=\sum_{k\geq 1}(k-1)!\frac{x^k}{k!}\).
都可以通过泰勒展开证明.
EXP的组合意义
我们设\(F_k(n)\)为\(n\)个有标号元素划分成\(k\)个非空无序集合的情况,\(f_i\)为\(i\)个元素组成一个集合的时候,其上特定组合结构的数量(就是一个一个只和\(|S|\)有关的定义在集合上的函数),有: \[ F_k(n)=\frac{n!}{k!}\sum_{\sum_{i=1}^ka_i=n}\prod_{j=1}^k\frac{f_{a_j}}{a_j!} \] 设\(\hat{F}(x)=\sum_{n\geq 0}f_n\frac{x^n}{n!}\),再设: \[ \hat G_k(x)=\sum_{n\geq 0}F_k(n)\frac{x^n}{n!}\\ =\sum_{n\geq 0}x^n\frac{1}{k!}\sum_{\sum_{i=1}^ka_i=n}\prod_{j=1}^k\frac{f_{a_j}}{a_j!}\\ =\sum_{n\geq 0}\frac{1}{k!}\sum_{\sum_{i=1}^ka_i=n}\prod_{j=1}^k\frac{f_{a_j}x^{a_j}}{a_j!}\\ =\frac{1}{k!}\hat F^k(x) \]
\[ \sum_{k\geq 0}\hat G_k(x)=\exp \hat F(x) \]
或者直接递推: \[ F_k(x)=\sum_{i=1}^{n-k+1}\binom{n}{i}F_{k-1}(n-i)f_i\frac{1}{k}\\ \]
\[ \hat G_k(x)=\sum_{n\geq 0}\frac{x^n}{n!}F_k(n)\\ =\sum_{n\geq 0}\frac{x^n}{n!}\sum_{i=1}^{n-k+1}\binom{n}{i}F_{k-1}(n-i)f_i\frac{1}{k}\\ =\frac{1}{k}\sum_{n\geq 0}\frac{x^n}{n!}\sum_{i=1}^{n-k+1}\binom{n}{i}F_{k-1}(n-i)f_i\\ =\frac{1}{k}\hat G_{k-1}(x)\hat F(x)\\ =\frac{1}{k!}\hat F^k(x) \]
简而言之,\([x^n]\hat F(x)\)是将\(n\)个有标号的元素放到同一个无序集合的方案数,而\([x^n]\exp \hat F(x)\)是将\(n\)个有标号的元素分成若干个无编号的非空无序集合的方案数.
Example
Example1(POJ3734)
对于红黄色砖块,其选取方案为\(\{1,0,1,0,\cdots\}\),对应的EGF是\(\frac{e^x+e^{-x}}{2}\).
对于蓝绿色砖块,选取方案是\(e^x\).
乘起来有: \[ \hat F(x)=(\frac{e^x+e^{-x}}{2})^2e^{2x}\\ =\frac{(e^{2x}+2+e^{-2x})e^{2x}}{4}\\ =\frac{e^{4x}+2e^{2x}+1}{4}\\ =\frac{1}{4}+\sum_{k\geq 0}\frac{4^i+2^{i+1}}{4}\frac{x^i}{i!} \] 于是有\([x^n]\hat F(x)=4^{n-1}+2^{n-1}\).
Example2(圆排列)
长度为\(n\)的排列数的指数生成函数是\(\hat P(x)=\sum_{n\geq 0}\frac{n!x^n}{n!}=\frac{1}{1-x}\).
长度为\(n\)的圆排列的指数生成函数是\(\hat Q(x)=\sum_{n\geq 0}\frac{(n-1)!x^n}{n!}=\frac{x^n}{n}=-\ln (1-x)=\ln\frac{1}{1-x}\).
于是有\(\exp\hat Q(x)=\hat P(x)\).
这个怎么理解呢?考虑一个排列可以分成若干个置换环,而一个集合能形成的置换环数量显然就是圆排列.
Example3(错排数)
从置换环的角度考虑,错排是指置换环中不存在自环的排列,也就是说不存在长度为\(1\)的置换环,其EGF显然是\(\sum_{n\geq 2}\frac{x^n}{n}=-\ln(1-x)-x\),错排数的EGF对其取\(\exp\)即可.
Example4(点带编号无向连通图计数)
考虑如果\(n\)个点带编号的无向连通图的EGF是\(\hat F(x)\),那么\(n\)个点带标号无向图的EGF就是\(\exp \hat F(x)\),后者直接计数,前者对后者做一次\(\ln\)就好.
Example5(不动点计数)
求有多少个映射\(f:\{1,2,\cdots,n\}\mapsto\{1,2,\cdots,n\}\)满足\(f\circ f\circ \cdots \circ f\)(共\(k\)个\(f\))\(=f\circ f\circ \cdots\circ f\)(共\(k-1\)个\(f\)).
考虑将\(i\rightarrow f_i\),这等价于对深度不超过\(k\)的基环树(环的长度为\(1\))计数,等价于对深度不超过\(k\)的有根树计数.注意到删去根节点后等价于对深度不超过\(k-1\)的有根树计数,因此\(\hat F_k(x)=x\exp \hat F_{k-1}(x)\).
Example6([CF891E]Lust)
假设\(k\)次操作后\(a_i\)减少了\(b_i\),实际上要求的就是\(\prod_{i=1}^na_i-\prod_{i=1}^n(a_i-b_i)\).
考虑对所有情况下的\(\prod_{i=1}^n(a_i-b_i)\)求和,注意到\(k\)次操作,使得\(i\)出现\(b_i\)次的方案数是\(\frac{k!}{\prod_{i=1}^nb_i!}\).直接设\(a_j\)的EGF是 \[ \hat F_{j}(x)=\sum_{i\geq 0}(a_j-i)\frac{x^i}{i!}\\=\sum_{i\geq 0}a_j\frac{x^i}{i!}-\sum_{i\geq 1}\frac{x^i}{(i-1)!}\\ =a_je^x-xe^x=(a_j-x)e^x \] 答案就是\([x^k]\prod_{j=1}^n\hat F_j(x)\).
Example7
狄利克雷生成函数(DGF)
对于序列\(f_n\),定义其DGF为\(\tilde F(x)=\sum_{i\geq 1}\frac{f_i}{i^x}\).注意到若\(f\)是积性函数,那么\(\tilde{F}(x)=\prod_{p\in prime}\sum_{i\geq 0}\frac{f_{p^i}}{p^{ix}}\\\).
基本运算
对于两个序列\(f,g\),其DGF之积对应的是两者的狄利克雷卷积序列的DGF: \[ \tilde{F}(x)\tilde{G}(x)=\sum_{i}\sum_{j}\frac{f(i)g(j)}{(ij)^x}\\ =\sum_{i}\frac{1}{i^x}\sum_{d|i}f(d)g(\frac{i}{d}) \]
封闭式
- \(\epsilon(x)=[x=1]\).
显然为\(\tilde{E}(x)=1\).
- \(I(x)=1\).
其封闭式是黎曼函数\(\zeta(x)\),事实上,我们有: \[ \zeta(x)=\prod_{i\geq 1}\frac{1}{i^x}\\=\prod_{p\in prime}\sum_{i\geq 0}\frac{1}{p^{ix}}\\=\prod_{p\in prime}\frac{1}{1-p^{-x}} \]
- \(\mu(n)\).
其DGF为\(\tilde{M}(x)=\prod_{p\in prime}(1-p^{-x})\).注意到\(\zeta(x)\tilde{M}(x)=1,\tilde{M}(x)=\frac{1}{\zeta(x)}\).
- \(id(n)=n\).
有\(\tilde{ID}(n)=\prod_{i\geq 1}\frac{i}{i^x}=\prod_{i\geq 1}\frac{1}{i^{x-1}}=\zeta(x-1)\).
- \(I_k(n)=n^k\).
\[ \tilde{I_k}(x)=\prod_{i\geq 1}\frac{1}{i^{x-k}}=\zeta(x-k) \]
- \(\varphi(n)\).
注意到: \[ \tilde{\Phi}(x)=\prod_{p\in prime}(1+\frac{p-1}{p^x}+\frac{p(p-1)}{p^{2x}}+\cdots)\\ =\prod_{p\in prime}\frac{1-p^{-x}}{1-p^{1-x}}\\ =\tilde{\Phi}(x)=\frac{\zeta(x-1)}{\zeta(x)} \] 也注意到\(\tilde{\Phi}(x)I(x)=\zeta(x-1)=\tilde{ID}(x)\).
- \(\sigma_k(n)=\sum_{d|n}d^k\).
注意到\(\sigma_k(n)=I_k(n)*I_0(n)\),也就是说\(\tilde{S}(x)=\zeta(x-k)\zeta(x)\).
- \(u(n)=|\mu(n)|\).
\(\tilde{u}(n)=\frac{\zeta(n)}{\zeta(2n)}\).
Example
Example1(luoguP3768)
考虑对于\(f(n)=n^2\varphi(n)\)构造积性函数\(g(n),h(n)\)使得\(f*g=h\).
注意到: \[ \tilde{F}(x)=\prod_{p\in prime}(1+\sum_{k\geq 1}\frac{p^{3k-1}(p-1)}{p^{kx}})\\=\prod_{p\in prime}\frac{1-p^{2-x}}{1-p^{3-x}}=\frac{\zeta(x-3)}{\zeta(x-2)} \] 也就是\(f*I_2=I_3\).
阶乘的扩展定义
对于复数的阶乘,我们通常定义: \[ \cfrac{1}{z!}=\lim_{n\rightarrow +\infin}\binom{n+z}{z}n^{-z} \] 同时我们定义\(\Gamma(z+1)=z!\),有:\((-z)!\Gamma(z)=\cfrac{\pi}{\sin(\pi z)}\).
这样我们还可以定义广义阶乘幂: \[ z^{\underline{w}}=\cfrac{z!}{(z-w)!}\\ z^{\overline{w}}=\cfrac{\Gamma(z+w)}{\Gamma(z)} \] 通过以上我们还可以有二项式系数的定义: \[ \binom{z}{w}=\lim_{\zeta\rightarrow z,\omega\rightarrow w}\cfrac{\zeta!}{\omega!(\zeta-\omega)!} \]
超几何级数
超几何函数
我们定义超几何函数\(F(a_1,...,a_m;b_1,...b_n;z)=F\left(\begin{array}{r|}a_1,...,a_m\\b_1,...,b_n\end{array}z\right)=\sum_{k\geq 0}\cfrac{z^k\prod_{i=1}^ma_i^{\overline{k}}}{k!\prod_{i=1}^nb_i^{\overline{k}}}\).
许多生成函数都可以写成超几何函数的形式.
值得一提的是,如果我们直接定义类似\(\cfrac{0}{0}=1\)之类的式子,可以发现当\(z=0\)时任意超几何函数总是\(=1\).
值得一提的是,我们通常直接忽略超几何函数中的任何特殊情况,例如分母为\(0\)或者哪里出现了正无穷.如同生成函数中我们不关心式子带入一个数后是否收敛而只关心是否两边存在一种对应的转化.如果你想去探究超几何函数中的各种情况,那请去翻那本巨大的、黑糊糊的、作者默认你精通高等数学的、你在第五章看到的恒等式作者在第七章才给出证明的《具体数学》,而不是看我这个弱智写的笔记.笔者看这一段的时候已经被作者的”严谨”态度整疯了.该证明的一拖再拖不该证明的可以一句话带过的逼逼逼逼.仿佛这本书就是写给那些已经会了所有东西只是来使自己已经学会的东西更加体系化的以及拿来查阅各种恒等式的工具书.
特殊的超几何函数
合流超几何函数
我们通常把形如\(M(a;b;z)=F\left(\begin{array}{r|}a\\b\end{array}z\right)=\sum_{k\geq 0}\cfrac{z^ka^{\overline{k}}}{b^{\overline{k}}k!}\)的函数称为合流超几何函数.
不难发现我们有: \[ F\left(\begin{array}{r|}1\\1\end{array}z\right)=e^z \] 也即常见生成函数中的\((6)\).
高斯超几何函数
我们把形如\(F\left(\begin{array}{r|}a,b\\c\end{array}z\right)=\sum_{k\geq 0}\cfrac{z^ka^{\overline{k}}b^{\overline{k}}}{c^{\overline{k}}k!}\)的函数称为高斯超几何函数.
下面是几种常见的高斯超几何函数形式:
- \(F\left(\begin{array}{r|}1,1\\1\end{array}z\right)=\cfrac{1}{1-z}\).
即常见生成函数\((1)\).
- \(F\left(\begin{array}{r|}-a,1\\1\end{array}-z\right)=(1+z)^a\).
即常见生成函数\((2)\).
- \(F\left(\begin{array}{r|}a,1\\1\end{array}z\right)=\cfrac{1}{(1-z)^a}\).
即常见生成函数\((4)\).
- \(F\left(\begin{array}{r|}1,1\\2\end{array}-z\right)=\cfrac {\ln(1+z)}z\).
即常见生成函数\((7)\).
超几何级数的应用
我们先考虑改写超几何级数的形式:
\(F\left(\begin{array}{r|}a_1,...,a_m\\b_1,...,b_n\end{array}z\right)=\sum_{k\geq 0}t_k,t_k=\cfrac{z^k\prod_{i=1}^ma_i^{\overline{k}}}{k!\prod_{i=1}^nb_i^{\overline{k}}}\).
不难发现\(t_0=1\),而: \[ \cfrac{t_{k+1}}{t_k}=\cfrac{z^{k+1}}{z^k}\cfrac{k!}{(k+1)!}\cfrac{\prod_{i=1}^ma_i^{\overline{k+1}}}{\prod_{i=1}^ma_i^{\overline{k}}}\cfrac{\prod_{i=1}^nb_i^{\overline{k}}}{\prod_{i=1}^nb_i^{\overline{k+1}}}\\ =\cfrac{\prod_{i=1}^m(k+a_i)}{\prod_{i=1}^n(k+b_i)}\cfrac{z}{k+1} \] 换句话说,\(\cfrac{t_{k+1}}{t_k}\)是关于\(k\)的一个有理函数.而根据代数基本定理,任意\(k\)的有理函数在\(\mathbb{C}\)内都可以分解为以上的形式(如果缺少\(k+1\)项则需要上下同时乘以\(k+1\)以补上).
换句话说,对于一个无穷级数\(\sum_{k\geq 0}t_k\),我们先将\(\cfrac{t_{k+1}}{t_k}\)表示回超几何函数,设为\(F\).
那么有:\(\sum_{k\geq 0}t_k=t_0F\).
好,接下来请把脑子扔了,不要纠结某一个公式按理来说只能作用于正整数而在这里直接将它套在了复数域上.你只需要知道数学家非常厉害通过扩展一些东西的定义(大部分是阶乘和\(\Gamma\)函数的定义)来使这些公式全部成立.But who cares,只要我们能用就行了.我又不是数竞人,这些麻烦的要死我直观上根本无法接受的定义交给数竞老哥证明得了.反正信竞更多依赖离散数学,大不了我们直接默认所有的数都是自然数.
Example
求证:\(\sum_{k\leq n}\binom{r+k}{k}=\binom{r+n+1}{n}\Leftrightarrow F\left(\begin{array}{r|}1,-n\\-n-r\end{array}1\right)=\cfrac{r+n+1}{r+1},n\in\mathbb{N}\\\).
首先考虑: \[ \sum_{k\leq n}\binom{r+k}{k}=\sum_{k\geq 0}\binom{r+n-k}{n-k} \] 有了这个无穷级数,我们可以直接将二项式系数用阶乘形式展开,于是得到: \[ \binom{r+n}{n}F\left(\begin{array}{r|}1,-n\\-n-r\end{array}1\right)=\binom{r+n+1}{n} \]
两边同时除以\(\binom{r+n}{n}\)得到上式.
二项式系数与超几何函数
通过范德蒙德卷积,不难验证: \[ F\left(\begin{array}{r|}a,b\\c\end{array}1\right)=\cfrac{\Gamma(c-a-b)\Gamma(c)}{\Gamma(c-a)\Gamma(c-b)},-b\in\mathbb{N} \] 这个公式的一个特例是: \[ F\left(\begin{array}{r|}a,-n\\c\end{array}1\right)=\cfrac{(c-a)^{\overline{n}}}{c^{\overline{n}}}=\cfrac{(a-c)^{\underline{n}}}{(-c)^{\underline{n}}},n\in\mathbb{N}\\ \sum_{k\geq 0}\cfrac{a^{\overline{k}}(-n)^{\overline{k}}}{c^{\overline{k}}k!}=\cfrac{(c-a)^{\overline{n}}}{c^{\overline{n}}}=\cfrac{(a-c)^{\underline{n}}}{(-c)^{\underline{n}}},n\in\mathbb{N}\\ \] 这个公式几乎囊括了所有的基本二项式求和公式:上指标求和,平行求和,范德蒙德卷积……几乎只要是我们推出的由两个及以下项的乘积求和的二项式系数相关的式子都可以使用这个式子.
那么如果我们要三项相乘或更多,我们有Saalschütz恒等式: \[ F\left(\begin{array}{r|}a,b,-n\\c,a+b-n-c+1\end{array}1\right)=\cfrac{(c-a)^{\overline{n}}(c-b)^{\overline{n}}}{c^{\overline{n}}(c-a-b)^{\overline{n}}}=\cfrac{(a-c)^{\underline{n}}(b-c)^{\underline{n}}}{(-c)^{\underline{n}}(a+b-c)^{\overline{n}}},n\in\mathbb{N}\\ \] 事实上,《具体数学》上给出了大量的超几何级数的应用以及各种技巧,但是笔者的智商已经理解不了接下来的内容了.考虑到大部分时候上述两个超几何级数恒等式已经足够解决绝大部分问题,如果考到更加困难的求和技巧,笔者相信别人也不会做,于是笔者决定摆烂.
求微分方程
Example1(luogu4931)
二项式反演: \[ ans_k=\sum_{i=k}^n(-1)^{i-k}\binom{i}{k}\binom{n}{i}\binom{n}{i}i!(2n-2i)!2^i\\ =\sum_{i=k}^n(-1)^{i-k}\frac{1}{k!(i-k)!}\frac{n!}{(n-i)!}\frac{n!}{(n-i)!}(2n-2i)!2^i\\ =(n!)^2\frac{2^k}{k!}\sum_{i=k}^n(-1)^{i-k}\frac{1}{(i-k)!}\binom{2n-2i}{n-i}2^{i-k}\\ =(n!)^2\frac{2^k}{k!}\sum_{i=0}^{n}\frac{(-2)^{i}}{i!}\binom{2n-2i}{n-i} \] 注意到后者只与\(n-k\)有关,不妨设其为\(f_{n}=\sum_{i=0}^{n}\frac{(-2)^{i}}{i!}\binom{2n-2i}{n-i}\),预处理一下就可以做到\(O(n^2+nT)\).
加强版咋做?我们继续看看式子: \[ ans=(n!)^2\frac{2^k}{k!}f_{n-k}\\ f_{n}=\sum_{i=0}^{n}\frac{(-2)^{i}}{i!}\binom{2n-2i}{n-i} \] 注意到\(f\)是一个卷积的形式,设其生成函数为\(F_n\),\(g_n=\frac{(-2)^n}{n!},h_n=\binom{2n}{n}\),我们自然有\(F=GH\).
考虑\(G\)和\(H\)的生成函数形式,先看\(G\),显然用泰勒展开: \[ G=\sum_{n\geq 0}\frac{(-2x)^n}{n!}=e^{-2x} \] 再看\(H\),是卡特兰数的生成函数,有: \[ H=\frac{1}{\sqrt{1-4x}} \] 这下简单了,答案是: \[ (n!)^2\frac{2^k}{k!}[x^{n-k}]\frac{e^{-2x}}{\sqrt {1-4x}} \] 现在看\(F\),平方一下有: \[ (1-4x)F^2=e^{-4x} \] 两边求导: \[ -4F^2+(1-4x)2F\times F'=-4e^{-4x}\\ -4F^2+(1-4x)2F\times F'=-4(1-4x)F^2\\ (2-8x)F'=16xF\\ \] 得到了一个线性递推形式,更进一步地: \[ 2(i+1)f_{i+1}-8if_i=16f_{i-1}\\ if_i=4(i-1)f_{i-1}+8f_{i-2} \] 技术总结一下:其实就是你想要得到一个递推式,然后注意到这玩意要写成微分方程的形式,所以开始往那边凑.
###生成函数的应用
求解递归关系
我们假设已经有了\(R(z)=\sum_{k\geq 0}g_kz^k\),并且\(R(z)=\cfrac{P(z)}{Q(z)}\),其中\(P(z)\)和\(Q(z)\)都是多项式,我们想要找到一种方式求解\([z^n]R(z)\).
考虑有理函数\(S(z)=\sum_{k=1}^m\cfrac{a_k}{1-\rho_kz}\\\),不难发现\([z^n]S(z)=\sum_{k=1}^ma_k\rho_k^n\\\).
那么可以证明,只要\(Q(z)=0\)无重根并且无零根,那么就存在一组系数满足\(S(z)=R(z)\).
我们这么定义”反射”运算,若\(Q(z)=\sum_{k=0}^mq_kz^k\\\),则其反射多项式为\(Q^R(z)=\sum_{k=0}^mq_kz^{m-k}\\\).
若\(Q(z)=q_0\prod_{k=1}^m(1-\rho_kz)\),则显然有\(Q^R(z)=q_0\prod_{k=1}^m(z-\rho_k)\\\).
那么显然这里求出来的这组数\(\rho\)就是\(S(z)\)中的那组\(\rho\).
而我们有\(a_k=\cfrac{-\rho_kP(\cfrac{1}{\rho_k})}{Q'(\rho_k)}\).
Example1
已知\(n!=\sum_{k}\binom{n}{k}g_{n-k},n\in\mathbb{N}\\\),求\(g_n\).
首先两边同时除以\(n!\)并将组合数用阶乘形式展开,我们有: \[ 1=\sum_{k}\cfrac{g_{n-k}}{k!(n-k)!}. \] 如果我们令\(D(z)=\sum_{k\geq 0}\cfrac{g_{k}}{k!}z^k\),则有: \[ \cfrac{1}{1-z}=e^zD(z)\\ D(z)=\cfrac{1}{1-z}e^{-z}\\ D(z)=(\sum_{k\geq 0}z^k)(\sum_{k\geq 0}(-1)^k\cfrac{z^k}{k!})\\ [z^n]D(z)=\sum_{k=0}^n\cfrac{(-1)^k}{k!} \] 于是\(g_n=n!\sum_{k=0}^n\cfrac{(-1)^k}{k!}\\\).
Example2([QOJ5169] 夹娃娃)
首先设\(F_i(x)\)为第\(i\)家的生成函数,这个是显然可以快速预处理出来的.令\(M=520\).
问题在于每次询问的时候求出答案呢?
这里有一个套路:我们在一开始就暴力做点值,最后拿拉格朗日插值求答案.中间大概把能预处理的都预处理一下.最后的问题在于:
第一,预处理点值的时候,一共有\(n\)个多项式,最高次数是\(M\),因此一共要插入\(nM\)个值,又要处理每个后缀,复杂度来到\(O(n^2M^3)\).这个问题是好解决的.我们只需要在带入点值的时候做一个后缀继承一类的东西,复杂度就可以来到\(O(n^2M^2)\).
第二,询问的时候需要找到所有对应的点值并暴力乘起来,复杂度来到\(O(n^2Mq)\).但\(n\)如此小,我们可以用指数级别的复杂度来优化,我们考虑预处理一下\(2^n\)的答案,复杂度来到\(O(nM2^nq)\).但是这个更不太行.那怎么办呢?我们把这个指数级别的东西分块一下.预处理复杂度来到\(O(\frac{n}{B}B2^BMnM)\),单次询问复杂度来到\(O(\frac{n}{B}Mnq)\).但这个预处理复杂度好像还是有点艰难.不过注意到如果做一个剪枝优化:如果总共的喜欢的店的个数乘以\(k\)要大于\(m\),就直接输出\(0\).预处理的时候块内部也做一个剪枝,然后发现就能过了(牛逼).
第三,拉格朗日插值的时候需要\(O((nM)^2q)\)的复杂度,不过由于点值可以自己控制,这个复杂度可以轻松降到\(O(nMq)\).
Example3([十二省联考 2019] 皮配)
首先注意到题目等价于规定一个阵营和一个排序的人数上下界.
我们可以将这四位导师分别记为\(xy,y,x,1\),这样最后判断幂在一个区间内的\(x\)和\(y\)前面的系数就行.
注意到如果没有学校有偏好,将生成函数卷起来后得到的答案就是\(\prod (x^{s_i}y^{s_i}+x^{s_i})+\prod(y^{s_i}+1)=(\prod (x^{s_i}+1))(\prod(y^{s_i}+1))\).也就是\(x\)和\(y\)是互相独立的,我们可以分开算.
对于那些有偏好的学校,我们暴力算就行.复杂度不会高于\(O(mk^2s)\).最后两部分合并一下.