生成函数

泰勒多项式

对于函数$f$，设他在点$x_0$处存在直到$n$阶的导数，构造一个$n$次多项式：

$T_n(x)=f(x_0)+\frac{f'(x_0)}{1!}(x-x_0)+\frac{f''(x_0)}{2!}(x-x_0)^2+...+\frac{f^{(n)}(x_0)}{n!}(x-x_0)^n\\T_n(x)=\sum_{i=0}^{i=n}\frac{f^{(i)}(x_0)}{i!}(x-x_0)^i$

当$x_0=0$时有麦克劳林公式

泰勒展开

函数$f$的泰勒多项式即为其泰勒展开

重要函数泰勒展开：

$e^x=\sum_{i=0}^{\infty}\frac{x^i}{i!}\\ ln(1+x)=\sum_{i=1}^{\infty}(-1)^{i+1}\frac{x^i}{i}\\ \frac{1}{1+x}=\sum_{i=0}^{\infty}(-1)^ix^i\\ \frac{1}{1-x}=\sum_{i=0}^{\infty}x^i\\ \frac{1}{1-qx}=\sum_{i=0}^{\infty}q^ix^i\\ (1+x)^a=\sum_{i=0}^{\infty}\frac{\prod_{j=1}^n(a-j+1)}{i!}x^i$

普通生成函数

对于一个无穷序列$a$，定义其普通生成函数为$\sum_{i=0}^{\infty}a_ix^i$

小练习：

1. 序列${1,0,1,0...}$的普通生成函数为$\sum_{i=0}^{\infty}x^{2i}=\sum_{i=0}^{\infty}(x^2)^{i}=\frac{1}{1-x^2}$

2. 序列${0,1,0,1...}$的普通生成函数为$x\sum_{i=0}^{\infty}x^{2i}=x\sum_{i=0}^{\infty}(x^2)^{i}=\frac{x}{1-x^2}$

序列右移普通生成函数乘以$x$，记得处理好常数项

3. 序列$1,2,3,...n,...$的普通生成函数为$\sum_{i=0}^{\infty}(i+1)x^i=\sum_{i=1}^{\infty}ix^{i-1}=\sum_{i=1}^{\infty}(x^i)'=(\sum_{i=0}^{\infty}x^i-1)'=(\frac 1 {1-x}-1)'=\frac{1}{(1-x)^2}$

   是不是怪复杂的，其实我们可以使用错位相减的思路

   设$S$为该序列普通生成函数

   $S=1+2x+3x^2+4x^3+...\\xS=0+x+2x^2+3x^3+...\\(1-x)S=1+x+x^2+x^3+...=\frac{1}{1-x}\\S=\frac{1}{(1-x)^2}$

4. 序列$1,3,5,7,...,2n-1,...$的普通生成函数为$S$

   $S=1+3x+5x^2+7x^3+...\\xS=0+x+3x^2+5x^3+...\\(1-x)S=1+2x+2x^2+2x^3+...=1+\frac{2x}{1-x}=\frac{1+x}{(1-x)^2}$

$\text{Fibonacci}$的普通生成函数：

$S=\frac1 {1-x-x^2}$

$Catlan$的普通生成函数：

$G=\sum_{i=0}^{\infty}c_ix^i=\sum_{i=0}^{\infty}c_{i+1}x^{i+1}+1\\=\sum_{i=0}^{\infty}\sum_{j=0}^{i}c_jc_{i-j} x^{i+1}+1=x\sum_{i=0}^{\infty}\sum_{j=0}^{i}c_jx^jc_{i-j}x^{i-j}+1\\=x\sum_{j=0}^{\infty}c_jx^j\sum_{i=j}^{\infty}c_{i-j}x^{i-j}+1$

令$k=i-j$

$G=x\sum_{j=0}^{\infty}c_jx^j\sum_{k=0}^{\infty}c_kx^k+1=xG^2+1$

$G=\frac{1\pm \sqrt{1-4x}}{2x}$

观察$G$的常数项，由于$x$非变量

考虑将$1-x$泰勒展开

$\sqrt{1-x}=1+\frac x 2-\frac {x^2} 8+...\\\sqrt{1-4x}=1-2x-2x^2+...$

若取加号

$G=\frac{2-2x-2x^2}{2x}=\frac 1 x-1-x$

常数项不对

取减号符合

故$G=\frac{1-\sqrt{1-4x}}{2x}$

将$G$泰勒展开整理一波可以得到$c_n$的通项

$c_n=\frac 1 {k+1}C_{2k}^k$

指数生成函数

对于一个无穷序列$a$，定义其普通生成函数为$\sum_{i=0}^{\infty}a_i\frac{x^i}{i!}$

普通生成函数通常用来解决无标号计数问题，指数生成函数通常用来解决带标号的计数问题。

排列数$\text{P},p_n=n!$的指数生成函数：$\frac 1 {1-x}$

圆排列数$\text{C}，c_n=(n-1)!$的指数生成函数：$ln(\frac{1}{1-x})$

注意到$P=e^C$，这是一个非常有趣的性质

考虑排列数和圆排列数的关系

将排列做一个置换群分解

每一个排列唯一对应一个置换群集合

对于确定的$n$个位置组成的置换，其方案数有$(n-1)!=c_n$即圆排列

故每一个排列能拆成若干个圆排列

可以证明像$\text P$这样能分解成若干个$\text C$的指数生成函数

$P=e^C$

eg:

$n$个点形成森林的方案数的指数生成函数为$\text F$

$n$个点形成树的方案数的指数生成函数为$\text T$

则$F=e^T$

错排数的指数生成函数$\text F$可以分解成若干个无自环的置换$\text D$

$D=C-x\\F=e^D$

$n$个点的有标号无向连通图个数的指数生成函数为$\text F$

$n$个点的有标号无向图个数的指数生成函数为$\text G$

则$G=e^F$

多项式

多项式的表示

小学我们就学过多项式的概念

例如$F(x)=x^2+2x+1$这就是一个二次多项式

多项式的系数表示法

这是一般的多项式常用的表示方法

对于一个$n$次多项式，我们可以用$n+1$个系数表示出这个多项式

例如上面的$F(x)$，我们可以用$1,2,1$表示这个多项式

多项式的点值表示法

我们可以把一个多项式理解成一个高次函数

对于每一个$x$我们都能得到这个函数的一个$y$值（点值）

对于一个$n$次多项式，我们可以用$n+1$个点值表示出这个多项式

例如上面的$F(x)$，我们可以用$1,4,9$来表示出这个多项式

多项式加法

即$F(x)+G(x)$,$F(x)$为$n$次多项式，$G(x)$为$m$次多项式，不妨设$n<m$

对于系数表示法，把两个多项式的系数相加即可

对于点值表示法，取$m$个不同的$x$值代入两个多项式得到的点值相加即可

多项式乘法

即$F(x)\times G(x)$,$F(x)$为$n$次多项式，$G(x)$为$m$次多项式，不妨设$n<m$

我们可以将多项式乘法理解为数字竖式乘法的形式

对于系数表示法，$O(nm)$枚举即可

对于点值表示法，取$n+m$个不同的$x$值代入两个多项式中得到的点值相乘即可

多项式乘法

FFT

快速傅里叶变换Fast Fast TLE

复数

了解这部分可以跳过

初一时我们学过实数的概念

我们也学过一元二次方程

当碰到$x^2+2x+2=0$这样$\Delta<0$的方程时

老师告诉我们这是无实数解的，因为负数在实数范围内没有平方根

但在复数范围内一切皆有可能

复数域也是目前最大的定义域

定义与复平面

我们把形如$z=a+bi$（$a,b$均为实数）的数称为复数，其中$a$称为实部，$b$称为虚部，$i$称为虚数单位。当$z$的虚部等于零时，常称$z$为实数；当$z$的虚部不等于零时，实部等于零时，常称$z$为纯虚数。

——摘自百度百科

我们可以把复数域映射到平面直角坐标系上，一般称该平面为复平面

用一个点$(a,b)$表示一个复数，对应$a+bi$

复数的三角形式

一个复数可以表示成$z=r(cos\theta+isin\theta)$的形式，$r$是$z$的模，$\theta$是$z$的辐角

复数的运算

$z_1=a_1+b_1i=r_1(cos\theta_1+isin\theta_1),z_2=a_2+b_2i=r_2(cos\theta_2+isin\theta_2)$

$z_1+z_2=(a_1+a_2)+(b_1+b_2)i\\z_1*z_2=(a_1*a_2-b_1*b_2)+(a_1*b_2+a_2*b_1)i\\z_1*z_2=r_1*r_2(cos(\theta_1+\theta_2)+isin(\theta_1+\theta_2))\\\frac{z_1}{z_2}=\frac{r_1}{r_2}(cos(\theta_1-\theta_2)+isin(\theta_1-\theta_2))$

具体推算过程可以去系统的学习一下复数，毕竟我们在搞OI

单位根

我们称方程$x^n=1$的所有复数解$\omega_n^k,k\in[0,n-1]$为$n$次单位根

$\omega_n^k=cos\frac{2k\pi}{n}+isin\frac{2k\pi}{n}$

显然$\omega_n^0=1$

性质

1.$(\omega_n^1)^k=\omega_n^k$

由定义易知

2.$\omega_n^k=\omega_{2n}^{2k}$

$\omega_{2n}^{2k}=cos\frac{4k\pi}{2n}+isin\frac{4k\pi}{2n}=cos\frac{2k\pi}{n}+isin\frac{2k\pi}{n}=\omega_n^k$

3.$\omega_n^k=-\omega_n^{k+\frac n 2},k<\frac n 2$

$\omega_n^{k+\frac n 2}=\omega_n^k*\omega_n^{\frac n 2}=\omega_n^k*(cos\pi+isin\pi)=-\omega_n^k$

FFT推导

问题叙述：

给定一个 $n$ 次多项式 $F(x)$，和一个 $m$ 次多项式 $G(x)$,求出 $F(x)$ 和 $G(x)$ 的卷积($F(x)\times G(x)$的每项系数)

$F(x)=a_0+a_1x+a_2x^2+...+a_nx^n\\G(x)=b_0+b_1x+b_2x^2+...+b_nx^m$

先将$F(x)$由系数表示法变成点值表示法，由于暴力是$O(n\times(n+m))$的，我们需要更优秀的做法

默认$n$为$2$的次幂

将$F(x)$按$x$幂次的奇偶性分离

记$F_0(x)=a_0+a_2x+a_4x^2+a_nx^{\frac n 2}\\F_1(x)=a_1+a_3x+a_5x^2+a_{n-1}x^{\frac n 2-1}$

则$F(x)=F_0(x^2)+xF_1(x^2)$

代入$x=\omega_n^k,x=\omega_n^{k+\frac n 2},k<\frac n 2$

$F(\omega_n^k)=F_0(\omega_n^{2k})+\omega_n^kF_1(\omega_n^{2k})$

$F(\omega_n^{k+\frac n 2})=F_0(\omega_n^{2k+n})+\omega_n^{k+\frac n 2}F_1(\omega_n^{2k+n})$

由$\omega_n^n=1$

$F(\omega_n^{k+\frac n 2})=F_0(\omega_n^{2k})+\omega_n^{k+\frac n 2}F_1(\omega_n^{2k})$

由$\omega_n^k=-\omega_n^{k+\frac n 2}$

$F(\omega_n^{k+\frac n 2})=F_0(\omega_n^{2k})-\omega_n^kF_1(\omega_n^{2k})$

我们惊喜的发现$F(\omega_n^k)$和$F(\omega_n^{k+\frac n 2})$的求式不同点只有$F_1(x)$这一项的系数互为相反数

而对于$F_0(x),F_1(x)$这两个多项式都可以重复上述过程继续奇偶分离做

这也是我们需要$n$为2的次幂的原因

void FFT(C *a,int lim,int opt){
	if(lim==1)return ;
	C a1[(lim>>1)+5],a2[(lim>>1)+5];
	for(int i=0;i<=lim;i+=2){
		a1[i>>1]=a[i];//F_0
		a2[i>>1]=a[i+1];//F_1
	}
	FFT(lim>>1,a1,opt);
	FFT(lim>>1,a2,opt);
	C w=(C){cos(2.0*pai/lim),opt*sin(2.0*pai/lim)};//lim次单位根
	C p=(C){1,0};
	for(int i=0;i<(lim>>1);i++,p=p*w){
		C t=p*a2[i];
		a[i]=a1[i]+t;
		a[i+(lim>>1)]=a1[i]-t;
	}
	return ;
}

我们能发现$\text{FFT}$合并的顺序为原顺序的二进制反转，得出非递归版，这个部分不过多叙述

void FFT(C *a,int lim,int opt){
	for(int i=0;i<lim;i++)if(i<r[i])swap(a[i],a[r[i]]);
	for(int mid=1;mid<lim;mid<<=1){//枚举中点
		C w=(C){cos(pai/mid),opt*sin(pai/mid)};
		int len=mid<<1;//长度
		for(int j=0;j<lim;j+=len){//每段起始位置
			C p=(C){1,0};
			for(int k=0;k<mid;k++,p=p*w){//每段前半段
				C u=a[j+k],v=p*a[j+mid+k];
				a[j+k]=u+v;
				a[j+mid+k]=u-v;
			}
		}
	}
	return ;
}

NTT

快速数论变换

由于复数运算常数巨大，且有精度问题，在模意义下，$\text{NTT}$利用原根完成和$\text{FTT}$完全相同的操作

void NTT(long long *f,int lim,int opt){
	for(int i=0;i<lim;i++)if(i<r[i])swap(f[i],f[r[i]]);
	for(int mid=1;mid<lim;mid<<=1){
		long long wn=power(opt==1?G:Gi,(mod-1)/(mid<<1));
		int len=mid<<1;
		for(int j=0;j<lim;j+=len){
			long long w=1;
			for(int k=0;k<mid;k++,w=w*wn%mod){
				long long u=f[j+k],v=w*f[j+k+mid]%mod;
				f[j+k]=(u+v)%mod;
				f[j+k+mid]=(u-v+mod)%mod;
			}
		}
	}
	if(opt==1)return ;
	long long inv=power(lim,mod-2);
	for(int i=0;i<lim;i++)f[i]=f[i]*inv%mod;
	return ;
}

这里放一份速度还行的预处理原根板子

int pw[2][4*maxn];
void pre(int lim){
	int c=0;
	for(int i=1;i<lim;i<<=1,c++){
		pw[0][i]=pw[1][i]=1;
		pw[0][i+1]=power(G,(mod-1)/(i<<1));
		pw[1][i+1]=power(Gi,(mod-1)/(i<<1));
		for(int j=2;j<i;j++){
			pw[0][i+j]=1ll*pw[0][i+j-1]*pw[0][i+1]%mod;
			pw[1][i+j]=1ll*pw[1][i+j-1]*pw[1][i+1]%mod;
		}
	}
	return ;
}
void NTT(int *f,int lim,int opt){
	for(int i=1;i<lim;i++)if(i<rev[i])swap(f[i],f[rev[i]]);
	int op=(opt==-1),c=0;
	for(int mid=1;mid<lim;mid<<=1,c++){
		for(int j=0;j<lim;j+=(mid<<1)){
			for(int k=0;k<mid;k++){
				int u=f[j+k],v=1ll*f[j+k+mid]*pw[op][mid+k]%mod;
				f[j+k]=add(u+v);
				f[j+k+mid]=sub(u-v);
			}
		}
	}
	if(opt==1)return;
	int inv=power(lim,mod-2);
	for(int i=0;i<lim;i++)f[i]=1ll*f[i]*inv%mod;
	return ;
}

任意模数多项式乘法

一种是三模NTT（做9次ntt），另一种是MTT（7次FFT或4次FFT）

MTT（拆系数FFT）

指毛爷爷在2016年国家集训队论文中给出的优秀任意模数多项式乘法优化

我们把两 $n\in[1,10^5]$ 次多项式系数值域定为 $[1,10^9]$ ，模数为 $[1,10^9]$ 的一个质数 $p$

那么答案是 $10^{23}$ 级别，double精度不够

考虑一个 $b\sim \sqrt w,w为值域$ 把系数分成两部分计算

$F(x)=bA(x)+B(x)\\G(x)=bC(x)+D(x)$

则

$F(x)G(x)=b^2A(x)C(x)+b(A(x)D(x)+B(x)C(x))+B(x)D(x)$

三个部分的多项式乘法值域为 $[1,10^{15}]$ ，double的精度足够处理

至此，我们得到了一个7次FFT的做法（对 $A,B,C,D$ 分别dft一次，对 $AC,AD+BC,BD$ 分别idft3次）

接下来考虑将两个多项式的点值表示由一遍dft得到

记 $P(x)=A(x)+iB(x)\\Q(x)=A(x)-iB(x)$

若得到了 $P,Q$ 两辅助多项式，我们通过加减即能得到 $A,B$

考虑 $P,Q$ 的关系

$P(\omega^k)=A(\omega^k)+iB(\omega^k)=\sum_{j=0}^na_j\omega^{jk}+ib_j\omega^{jk}\\=\sum_{j=0}^n(a_j+ib_j)(\cos\frac{2\pi jk}{n}+i\sin \frac{2\pi jk}{n})$

设 $X=\cos\frac{2\pi jk}{n}+i\sin \frac{2\pi jk}{n}$

$P(\omega^k)=\sum_{j=0}^n(a_j+ib_j)(\cos X+i\sin X)=\sum_{j=0}^na_j\cos X+ia_j\sin X+ib_j\cos X-b_j\sin X\\=\sum_{j=0}^na_j\cos X-b_j\sin X+i(a_j\sin X+b_j\cos X)$

$Q(\omega^k)=\sum_{j=0}^n(a_j-ib_j)(\cos X+i\sin X)=\sum_{j=0}^na_j\cos X+ia_j\sin X-ib_j\cos X+b_j\sin X\\=\sum_{j=0}^na_j\cos X+b_j\sin X+i(a_j\sin X-b_j\cos X)$

记 $\text{conj}(x)$ 表示 $x$ 的共轭复数

$Q(\omega^{n-k})=\sum_{j=0}^na_j\cos X-b_j\sin X-i(a_j\sin X+b_j\cos X)=\text{conj}(P(\omega^k))$

那么我们对 $P$ dft一次就能得到 $P,Q$ 的点值表达了!

我们成功的得到了一个一次dft，一次idft求卷积的神必做法

同时，我们也得到了两次dft，两次idft求任意模数多项式乘法的神必做法！

多项式求导与不定积分

void dervt(int lim,long long *f){
	for(int i=0;i<lim-1;i++)f[i]=f[i+1]*(i+1)%mod;
	f[lim-1]=0;
	return ;
}
void integ(int lim,long long *f){
	for(int i=lim-1;i>=1;i--)f[i]=f[i-1]*power(i,mod-2)%mod;
	f[0]=0;
	return ;
}

多项式求逆

【模板】多项式乘法逆

即给定$n-1$次多项式$\text{F(x)}$，求多项式$\text{G(x)}$满足，$\text{F(x)}*\text{G(x)}\equiv1\mod x^n$

考虑递归求解

已知

$\text H\\\text{F}*\text{H}\equiv1\mod x^{\frac n 2}\\\text{F}*\text{G}\equiv1\mod x^n$

$\text{G}-\text{H}\equiv0\mod x^{\frac n 2}\\(\text{G}-\text{H})^2\equiv0\mod x^n\\\text{G}^2-2\text{GH}+\text{H}^2\equiv 0 \mod x^n\\\text{G}-2\text{H}+\text{FH}^2\equiv0\mod x^n\\\text G\equiv2\text H-\text {FH}^2\mod x^n$

时间复杂度$T(n)=T(\frac n 2)+O(nlogn)=O(nlogn)$

long long A[maxn<<2];
void inv(int n,long long *f,long long *g){
	if(n==1){g[0]=power(f[0],mod-2);return ;}
	inv((n+1)>>1,f,g);
	int lim=1,k=0;
	while(lim<(n<<1))lim<<=1,k++;
	for(int i=1;i<lim;i++)r[i]=r[i>>1]>>1|((i&1)<<k-1);
	for(int i=0;i<n;i++)A[i]=f[i];
	for(int i=n;i<lim;i++)g[i]=A[i]=0;
	NTT(g,lim,1);NTT(A,lim,1);
	for(int i=0;i<lim;i++)g[i]=(2ll*g[i]%mod-A[i]*g[i]%mod*g[i]%mod+mod)%mod;
	NTT(g,lim,-1);
	for(int i=n;i<lim;i++)g[i]=0;
	return ;
}

多项式开根

【模板】多项式开根

即给定$n-1$次多项式$\text{F(x)}$，求多项式$\text{G(x)}$满足，$\text{G(x)}^2\equiv \text{F(x)}\mod x^n$

同样递归求解

已知

$\text H\\\text H^2\equiv \text F\mod x^{\frac n 2}\\\text G^2\equiv \text F\mod x^n$

$\text G\equiv \text H\mod x^{\frac n 2}\\\text G-\text H\equiv0\mod x^{\frac n 2}\\\text G^2-2\text{GH}+\text H^2\equiv 0 \mod x^n\\\text G\equiv\frac{\text F+\text H^2}{2\text H}$

求逆即可

long long B[maxn<<2],C[maxn<<2];
long long inv2=power(2,mod-2);
void sqrt(int n,long long *f,long long *g){
	if(n==1){g[0]=1;return ;}
	sqrt((n+1)>>1,f,g);
	inv(n,g,B);
	int lim=1,k=0;
	while(lim<(n<<1))lim<<=1,k++;
	for(int i=1;i<lim;i++)r[i]=r[i>>1]>>1|((i&1)<<k-1);
	for(int i=0;i<n;i++)C[i]=f[i];
	for(int i=n;i<lim;i++)B[i]=C[i]=0;
	NTT(g,lim,1);NTT(B,lim,1);NTT(C,lim,1);
	for(int i=0;i<lim;i++)g[i]=(C[i]+g[i]*g[i]%mod)%mod*inv2%mod*B[i]%mod;
	NTT(g,lim,-1);
	for(int i=n;i<lim;i++)g[i]=0;
	return ;
}

多项式$\text{ln}$

【模板】多项式对数函数（多项式 ln）

即给定$n-1$次多项式$\text{F(x)}$，求多项式$\text{G(x)}$满足，$\text{G(x)}\equiv \text{ln F(x)}\mod x^n$

与前两种思路不太一样，对两边求导

$\text G'\equiv\frac {\text F'}{\text F}\mod x^n$

求逆+求导+不定积分即可

long long D[maxn<<2];
void ln(int n,long long *f,long long *g){
	for(int i=0;i<n;i++)D[i]=f[i];
	inv(n,D,g);
	dervt(n,D);
	int lim=1,k=0;
	while(lim<(n<<1))lim<<=1,k++;
	for(int i=1;i<lim;i++)r[i]=((r[i>>1]>>1)|((i&1)<<(k-1)));
	NTT(D,lim,1);NTT(g,lim,1);
	for(int i=0;i<lim;i++)g[i]=D[i]*g[i]%mod;
	NTT(g,lim,-1);
	integ(n,g);
	for(int i=n;i<lim;i++)g[i]=0;
	for(int i=0;i<lim;i++)D[i]=0; 
	return ;
}

牛顿迭代

即给定$n-1$次多项式$\text{F(x)}$，求多项式$\text{G(x)}$满足，$\text{F(G(x))}\equiv 0\mod x^n$

同样递归求解

已知

$\text{H(x)}\\\text{F(H(x))}\equiv 0\mod x^{\frac n 2}$

将$\text{F(G(x))}$在$\text{H(x)}$处泰勒展开

$F(G(x))=\sum_{i=0}^{i=n}\frac{F^{(i)}(H(x))}{i!}(G(x)-H(x))^i\equiv 0 \mod x^n$

由于 $G(x)-H(x)$ 的最低非0系数项为 $x^{\frac n 2}$

则对于任意 $i\geq 2,(G(x)-H(x))^i\equiv 0\mod x^n$

故 $F(G(x))\equiv H(x)-\frac{F(H(x))}{F'(H(x))} \mod x^n$

多项式$\text{exp}$

【模板】多项式指数函数（多项式 exp）

即给定$n-1$次多项式$\text{F(x)}$，求多项式$\text{G(x)}$满足，$\text{G(x)}\equiv e^\text{F(x)}\mod x^n$

两边同时取$\text{ln}$

$\text{ln G}\equiv \text F \mod x^n$

定义$\text{H(x)}=\text{ln x-F}$，则

$\text{H(G)}\equiv 0\mod x^n$

牛顿迭代

long long E[maxn<<2],F[maxn<<2];
void exp(int n,long long *f,long long *g){
	if(n==1){g[0]=1;return ;}
	exp((n+1)>>1,f,g);
	ln(n,g,E);
	int lim=1,k=0;
	while(lim<=(n<<1))lim<<=1,k++;
	for(int i=1;i<lim;i++)r[i]=((r[i>>1]>>1)|((i&1)<<(k-1)));
	for(int i=0;i<n;i++)F[i]=f[i];
	for(int i=n;i<lim;i++)E[i]=F[i]=0;
	for(int i=0;i<lim;i++)F[i]=((F[i]-E[i])%mod+mod)%mod;
	F[0]++;
	NTT(g,lim,1);NTT(F,lim,1);
	for(int i=0;i<lim;i++)g[i]=g[i]*F[i]%mod;
	NTT(g,lim,-1);
	for(int i=n;i<lim;i++)g[i]=0;
	for(int i=0;i<n;i++)E[i]=0;
	return ;
}

多项式快速幂

【模板】多项式快速幂

long long H[maxn<<2];
void power(int n,int k,long long *f,long long *g){
	ln(n,f,g);
	for(int i=0;i<n;i++)g[i]=g[i]*k%mod;
	exp(n,g,H);
	for(int i=0;i<n;i++)g[i]=H[i];
	return ;
}

多项式除法

多项式多点求值

多项式多点插值

多项式复合逆