生成函数
多项式
形如$sum_{i=0}^{n}a_i x^i$的代数式称为n阶多项式
核函数
{ai}的核函数为f(x),它的生成函数为sigma(ai*f(i)*x^i)
生成函数的加减
{ai}{bi}的生成函数为A(x),B(x)
{ai+/-bi}的生成函数为A(x)+/-B(x)
生成函数的乘法
{ai}{bi}的卷积的生成函数是A(x)B(x)
普通生成函数
$A(x)=sum a_i x^i$
指数型生成函数
$A(x)=sum frac{a_i x^i}{i!}$
特殊的生成函数
有标号有向图计数$A(x)=sum frac{a_i x^i}{i!*2^{i*(i-1)/2}}$
狄利克雷生成函数$A(x)=sum_{i=1}frac{a_i}{i^{x}}$
概率生成函数$Gx(z)=sum Pr(X=k) z^{k}$
牛顿生成函数$C(x)=sum f(x)C(x,i)$
多项式
多项式的表示方法
系数表示方法
形如$sum_{i=0}^{n} ai x^{i}$的代数式
点值表示方法
对于k次多项式,给出在k+1个地方的取值,可以唯一确定多项式
证明:考虑这k+1个点值相同的一个k阶多项式,两个k阶多项式相减,得到k+1个零点的一个多项式,利用代数基本定理,该多项式为0,k+1个点值相同的k阶多项式是唯一的.
点值表示下多项式的运算
多项式加减 O(n)对应位置点值加减即可
多项式乘法 O(n)对应位置点值相乘即可
多项式系数点值转化
复数
记i^2=-1,复数形如a+bi
复数运算
加法:$(a+bi)+(c+di)=(a+c)+(bi+di)$
减法:$(a+bi)-(c+di)=(a-c)+(bi-di)$
乘法:$(a+bi)(c+di)=(ac-bd)+(ad+bc)i$
单位根
复平面中,记wn是幅角最小的n次单位根
显然$wn^{k}$也是n次单位根
代数基本定理$x^{n}=1$的解一共有n个,所以得到了所有的n次单位根
这n个n次单位根,以原点为圆心,1为半径作圆,所得单位圆的n个等分点
易知 $w_{n}^{k}=cos(frac{k*2pi}{n})+i sin(frac{k*2pi}{n})$
性质1:$w_{2n}^{2k}=w_{n}^{k}$
性质2:$w_{n}^{k+frac{n}{2}}=-w_{n}^{k}$
快速傅里叶变换fft
考虑多项式A(x)的点值表示,我们尝试求$A(w_n^0),A(w_n^1),A(w_n^2),...,A(w_n^(n-1)$
设$A(x)=sum_{i=0}^{n-1}aix^i$
下标奇偶分类，写成
$A(x)=sum_{i=0}^{2k}a_ix^i+xsum_{i=0}^{2k}a_{i+1}x^i$
$A1(x)=sum_{i=0}^{k}a_{2i}x^i$ $A2(x)=sum_{i=0}^{k}a_{2i+1}x^i$
则A(x)=A1(x^2)+xA2(x^2)
设$k<frac{n}{2}$ 现在要求$A(w_n^k)$
$A(w_n^k)=A1(w_n^{2k})+w_n^{k} A2(w_n^{2k})=A1(w_{frac{n}{2}}^{k})+w_n^{k} A2(w_{frac{n}{2}}^{k})$
$A(w_n^{k+frac{n}{2}})=A1(w_n^{2k+n})+w_n^{k+frac{n}{2}} A2(w_n^{2k+n})=A1(w_{frac{n}{2}}^{k})-w_n^{k} A2(w_{frac{n}{2}}^{k})$
只要知道A1(x),A2(x) 在$w_{frac{n}{2}}^0$ $w_{frac{n}{2}}^1 ... w_{frac{n}{2}}^{frac{n}{2}-1}$处点值,可O(n)推出A(x)在$w_n^0...w_n^{n-1}$处点值。不难发现A1(x),A2(x)是递归子问题,递归计算即可。T(n)=2T(n/2)+O(n) T(n)=O(nlogn)
傅里叶逆变换idft
我们要把点值表示转化成系数表示
设$A(x)=sum_{i=0}^{n-1}aix^i$ 且$yi=A(w_n^i)$ 现在已知$y0,...,y_{n-1}$,想反推$a0,...,a_{n-1}$
设$c_k=sum_{i=0}^{n-1}yi(w_n^{-k})^i$ 即多项式$B(x)=sum_{i=0}^{n-1}y_ix^i$在$w_n^0,w_n^{-1},...,w_n^{-k}$处的点值表示
展开上式可知
$c_k=sum_{i=0}^{n-1}yi(w_n^{-k})^i=sum_{i=0}^{n-1}(sum_{j=0}^{n-1}aj(w_n^i)^j)(w_n^{-k})^i=sum_{i=0}^{n-1}(sum_{j=0}^{n-1}aj(w_n^j)^i)(w_n^{-k})^i=sum_{i=0}^{n-1} sum_{j=0}^{n-1}aj(w_n^{j-k})^i=sum_{j=0}^{n-1}aj(sum_{i=0}^{n-1}(w_n^{j-k})^i)$
记$S(w_n^k)=sum_{i=0}{n-1}(w_n^k)^i$
当$k eq0$两边同乘$w_n^k$ $w_n^k S(w_n^k)=sum_{i=1}{n}(w_n^k)^i$
所以$S(w_n^k)=frac{(w_n^k)^n-1}{w_n^k-1}=0$ 即当$k eq0$,$S(w_n^k)=0$,否则$S(w_n^k)=n$
再看上式 $c_k=sum_{j=0}{n-1}S(w_n^{j-k})=n*a_k$
故用单位根的倒数替代单位根做dft,再把每个数/n,即为逆变换结果.
本质
向量左乘傅里叶矩阵和傅里叶逆矩阵,傅里叶矩阵和傅里叶逆矩阵有特殊性质.
快速数论变换ntt
注意到在fft中用到复数域上单位根的性质
如果在取模意义下,可以使用模意义下单位根(设G是原根,则wn为$G^{frac{p-1}{n}}$)
bzoj 5372
bzoj 4827
Byteasar 组建了一支舰队！他们现在正在海洋上航行着。海洋可以抽象成一张n×m 的网格图，其中有些位置是“.”，表示这一格是海水，可以通过；有些位置是“#”，表示这一格是礁石，不可以通过；有些位置是“o”，表示这一格目前有一艘舰，且舰离开这一格之后，这一格将变为“.”。这些“o” 表示Byteasar 的舰队，他们每天可以往上下左右中的一个方向移动一格，但不能有任何一艘舰驶出地图。特别地，Byteasar 对阵形有所研究，所以他不希望在航行的过程中改变阵形，即任何时刻任何两艘舰的相对位置都不能发生变化。Byteasar 的舰队可以航行无限长的时间，每当一艘舰经过某个格子的时候，这个格子海底的矿藏都将被Byteasar 获得。请写一个程序，帮助Byteasar 计算他最多可以获得多少个格子海底的矿藏？n,m<=700
循环卷积
因为wn^(n+k)=wn^k，如果有wn，可以做%(x^n)意义下的循环卷积。
例题1
给你一张M个点的图,图中任意一条从S到T的长度为K的倍数的路径会对答案产生C(n,len)的贡献,路径可以经过重复的边。答案对P取模。M<=10,K<=1000,P=1(mod K),N<=10^18
考虑如何处理C(n,len)，可以认为是在长度为len的路径上走走停停，选择n个时刻中的len个走，有状态i,j表示当前在i点走的步数%K余j,暴力矩阵乘法复杂度O(M^3K^3logN)，发现%K余j只会转移到j+1，可以优化，认为状态i有一个多项式F，fj表示%K余j的方案数，每次矩阵乘法多项式对应卷积即可O(M^3K^2logN)或O(M^3KlogKlogN)，发现P=1(mod K)，所以存在模P意义下K次单位根,可以进行循环卷积，考虑矩阵乘法中直接用点值可以做到O(M^3KlogN)，用$O(K^{2})$在开始处理求值和最后S到T的插值即可。
例题2
有N个人在玩猜拳游戏。每个人都有一个长度为K的出拳序列，序列里的每个元素是R,P或S，表示他们出的是石头，剪刀还是布。每个人的出拳序列都是循环的，即他们会不断地重复他们的出拳序列。两个人之间是好的当且仅当他们两个人从他们出拳序列任意地方开始出拳，循环地进行了K场比赛之后，三元组（赢的场数，输的场数，平的场数）都一样。问有多少个不同的这N个人的子集，是的他们两两之间都是好的。答案对1e9+7取模。N<=1e5，K<=15
令w为1的三次单位根,令w^2表示石头,令w^1表示剪刀,令w^0表示布,可以把每个出拳序列写成多项式的形式。2个出拳序列是好的，当且仅当其中一个出拳序列的多项式系数全部取倒数后,他们的循环卷积出的多项式每一位都相同。考虑一个每一位都一样的多项式在fft后只有1的点值非0。可以对每个出拳序列暴力插值后得出K+1个点值,我们把1的点值扔掉后对于剩下的K个点值压缩成1个0/1状态表示它这一位是否是0，我们可以依此暴力子集dp，可以得到$O(3^{K})$的做法。
codeforces 1010F
关于多项式的更多操作
分治fft
cdq分治+fft
多项式求逆
bzoj 3456
刚刚解决完电力网络的问题, 阿狸又被领导的任务给难住了.刚才说过, 阿狸的国家有n个城市, 现在国家需要在某些城市对之间建立一些贸易路线, 使得整个国家的任意两个城市都直接或间接的连通.为了省钱, 每两个城市之间最多只能有一条直接的贸易路径. 对于两个建立路线的方案, 如果存在一个城市对, 在两个方案中是否建立路线不一样, 那么这两个方案就是不同的, 否则就是相同的. 现在你需要求出一共有多少不同的方案.好了, 这就是困扰阿狸的问题. 换句话说, 你需要求出n个点的简单(无重边无自环)无向连通图数目.由于这个数字可能非常大, 你只需要输出方案数mod 1004535809(479*2^21+1)即可.
Sol1 考虑dp，fi表示i个点的连通无向图个数,考虑容斥，枚举第1个点所在的连通分量大小，$fn=2^{frac{n*(n-1)}{2}}-sum C(n-1,i-1)*fi*2^{frac{(n-i)(n-i-1)}{2}}$,cdq分治+fft.
Sol2 考虑fi的指数生成函数*i, $frac{fn}{(n-1)!}=frac{2^{frac{n*(n-1)}{2}}}{(n-1)!}-sum_{i=1}^{n-1} frac{fi}{(i-1)!}*frac{2^{frac{(n-i)*(n-i-1)}{2}}}{(n-i)!}$ $Hn=An-sum_{i=1}^{n-1} H_i*B_{n-i}$ 设$B0=1$ $H0=0$ $H*B=A$ $H=A*B^{-1}$.多项式求逆.
Sol3 考虑n个点的连通无向图个数的指数生成函数F，n个点的无向图个数的指数生成函数H，容易发现$e^{F}=H$，所以F=lnH.多项式求ln.
bzoj 4555
在2016年，佳媛姐姐刚刚学习了第二类斯特林数，非常开心。现在他想计算这样一个函数的值:.png){kind=small}
多项式除法
codechef RNG
Another way to write a RNG is to use linear recurrence relation.Let's consider the following linear recurrence:Ai=(Ai−1×C1+Ai−2×C2+...+Ai−k×Ck) mod 104857601,for i=k+1,k+2,...,where k is a positive integer.You are given initial values A1,A2,...,Ak and the coefficients C1,C2,...,Ck.Then the RNG can be used to generate any Ai for i larger than k.Your task is to calculate AN for a given N.
常系数线性递推
泰勒展开
多项式牛顿迭代
考虑给定多项式F(x)，找出G(x)使得$F(G(x))=0(mod x^n)$
考虑倍增,设$F(G_t(x))=0(mod x^{2^t})$
要求$G_{t+1}(x)$使得$F(G_{t+1}(x))=0(mod x^{2^{t+1}})$
把$F(G_{t+1}(x))$在$F(G_t(x))$处Taylor展开(可以和Taylor展开类似地用拉格朗日中值定理证明)
$F(G_{t+1}(x))=F(G_t(x))+Fprime(G_t(x))(G_{t+1}(x)-G_t(x))+Fprimeprime(G_t(x))(G_{t+1}(x)-G_t(x))^2+...$
因为 $(G_{t+1}(x)-G_t(x))=0(mod x^{2^t})$
所以 $(G_{t+1}(x)-G_t(x))^k=0(mod x^{2^{t+1}}) (k>1)$
所以 $G_{t+1}(x)=G_t(x)-frac{F(G_t(x))}{Fprime(G_t(x))}(mod x^(2^(t+1)))$
多项式牛顿迭代推导多项式操作
多项式求逆
多项式开方
多项式ln
多项式exp
多项式多点求值
多项式多点插值
例题3
长度为n的序列,m个操作,每次区间乘等差数列,输出最后每个数%998244353
FWT
FMT
州区划分
