重拳出击

前言

OI生涯中最大的坑。~~虽然我觉得填不上了~~

我的学习笔记真是越写越烂：缺少证明、漏洞百出。

难得要专攻算法了，（大概）会写的详细点。

抄袭来源

https://www.luogu.com.cn/blog/command-block/ntt-yu-duo-xiang-shi-quan-jia-tong

sls的课件

https://www.luogu.com.cn/blog/lx-2003/generating-function

https://www.luogu.com.cn/blog/lx-2003/generating-function-advanced

#define

以下，代码以mod表示模数，其他地方以$p$表示模数。

$g$为模$p$意义下的原根，$ig$为$g^{-1}$。

$tr$：$FFT/NTT$用的反转数组。

多项式全家桶

再次复读又又的励志语录：

“大声大声！熟练熟练！”

为了封装完整，保证多次调用函数不会有影响，我的写法常数不小，也很丑，将就着看吧。

找原根

$g$为模$p$意义下的原根，需要满足$\forall d|(p-1)\land d\neq p-1,g^d\not\equiv1\pmod p$。

而且最小的原根一般都比较小，只检验$100$以内的数即可：

const int mod = 998244353;
inline int quickpow(int x,int y=mod-2){
    int ans=1;
    while(y){
        if(y&1)ans=1ll*ans*x%mod;
        x=1ll*x*x%mod,y>>=1;
    }
}
bool check(int x){
    for(register int i=2;i*i<mod;++i)
        if((mod-1)%i==0&&(quickpow(x,i)==1||quickpow(x,(mod-1)/i)==1))return 0;
    return 1;
}
int getG(){
    for(register int i=2;i<=100;++i)if(check(i))return i;
}

FFT/NTT

详见FFT/NTT学习笔记~~（虽然我只是粘了个板子啥都没讲）~~

一般用不着$FFT$就只放$NTT$辣。

int tr[maxn];
inline int qm(int x){return x>=mod?x-mod:x;}
void NTT(int *f,int n,bool t){//f为多项式；n为多项式项数；t=0为dft，否则为idft
    for(register int i=0;i<n;++i)if(i<tr[i])swap(f[i],f[tr[i]]);
    for(register int p=2;p<=n;p<<=1){
        int len=p>>1,o=quickpow(t?ig:g,(mod-1)/p);
        for(register int i=0;i<n;i+=p){
            int gen=1,cop;
            for(register int j=i;j<i+len;++j){
                cop=1ll*f[j+len]*gen%mod,gen=1ll*gen*o%mod;
                f[j+len]=qm(f[j]+mod-cop),f[j]=qm(f[j]+cop);
            }
        }
    }
    if(t){
        int inv=quickpow(n);
        for(register int i=0;i<n;++i)f[i]=1ll*f[i]*inv%mod;
    }
}

乘法

就是把$NTT$板子封装成函数。

int A[maxn],B[maxn];
void mul(int *a,int *b,int *c,int n,int lim){//长度为n的多项式a和b相乘，结果前lim位保存在c中
    for(register int i=0;i<n;++i)A[i]=a[i],B[i]=b[i];
    int m=n<<1;
    n=1;
    while(n<m)n<<=1;
    for(register int i=0;i<n;++i)tr[i]=(tr[i>>1]>>1)|(i&1?n>>1:0);
    NTT(A,n,0),NTT(B,n,0);
    for(register int i=0;i<n;++i)A[i]=1ll*A[i]*B[i]%mod;
    NTT(A,n,1);
    for(register int i=0;i<lim;++i)c[i]=A[i];
    for(register int i=0;i<n;++i)A[i]=B[i]=0;
}

泰勒公式

用多项式来拟合函数：

若$f(x)$在$x_0$处可$n$阶导，有：

$f(x)=R_n(x)+\sum\limits_{i=0}^n\dfrac{f^{(i)}(x_0)}{i!}(x-x_0)^i$

其中$f^{(i)}(x)$表示$i$阶导数，$R_n(x)$是余项（毕竟拟合是有误差的）

若能无限求导，有：

$f(x)=\sum\limits_{i=0}^\infty \dfrac{f^{(i)}(x_0)}{i!}(x-x_0)^i$

一般取$x_0=0$计算方便，这时也叫麦克劳林公式。

牛顿迭代

根据泰勒公式得出来的。

已知多项式$G(x)$，求多项式$F(x)$满足$G(F(x))\equiv 0\pmod {x^n}$（$\bmod {x^n}$表示只考虑前$n$项）

倍增求解。假设已经求出$G(F^*(x))\equiv 0\pmod {x^{\frac{n}{2}}}$，要求$G(F(x))\equiv 0\pmod{x^n}$。

有$F(x)\equiv F^*(x)-\dfrac{G(F^*(x))}{G’(F^*(x))}\pmod{x^n}$

泰勒公式和牛顿迭代的证明不写了，网上到处都是。

求逆

已知多项式$F$，求出多项式$G$满足$F\times G\equiv 1\pmod {x^n}$。

倍增求解。当多项式只有常数项时，直接求出常数项的逆元即可。

可以用牛顿迭代来推：

$F(x)G(x)-1\equiv 0$

令$H(G(x))=F(x)G(x)-1$

$F(x)$已知，实际上是个系数，求完导后$G(x)$就没了，所以$H’(G(x))=F(x)$。

直接把牛顿迭代套上去：

$G(x)\equiv G^*(x)-\dfrac{H(G^*(x))}{H’(G^*(x))}\equiv G^*(x)-\dfrac{F(x)G^*(x)-1}{F(x)}\equiv G^*(x)-G(x)(F(x)G^*(x)-1)$

由于$F(x)G^*(x)-1\equiv 0\pmod{x^{\frac{n}{2}}}$即$F(x)G^*(x)-1$的前$\frac{n}{2}$为$0$。

所以$G(x)$乘上去的时候，在$\bmod{x^n}$时它的后$\frac{n}{2}$项是没有用的，用$G^*(x)$代替它。

于是$G(x)\equiv G^*(x)-G^*(x)(F(x)G^*(x)-1)\equiv (2-F(x)G^*(x))G^*(x)$

或者平方法推式子：

假设已知$F\times R’\equiv 1\pmod {x^{\frac{n}{2}}}$

要求$R$满足$F\times R\equiv 1\pmod{x^n}$

显然$R\equiv R’\pmod {x^{\frac{n}{2}}}$

$R-R’\equiv 0\pmod {x^{\frac{n}{2}}}$

两边平方，扩展到$x^n$：

$(R-R’)^2\equiv 0\pmod {x^n}$

$R^2-2RR’+R’^2\equiv 0\pmod {x^n}$

两边都乘一个$F$，由于是$\bmod x^n$，$F\times R$可以消掉，但$F\times R’$不能。

$R\equiv 2R’-FR’^2\pmod {x^n}$

于是可以愉快地扩展了。

此时我们发现要做$2$遍多项式乘法，$6$遍$NTT$。虽然可以把$R’^2$优化成$2$次效果也不大。

但其实可以先两遍$DFT$把$F$和$R’$转成点值，然后对点值做上面的运算，最后$IDFT$回去，只需要$3$遍$NTT$。

时间复杂度为$T(n)=T(\frac{n}{2})+O(n\log n)=O(n\log n)$，不是很明白为啥有人觉得是$\log^2$，是$T(\frac{n}{2})$不是$2T(\frac{n}{2})$啊。

肝了一上午终于把迭代+$3$次$NTT$版本搞出来了

int invR[maxn],_invR[maxn];
void inv(int *f,int *g,int n){//对项数为n的多项式f求逆，结果保存在g中
#define R invR
#define _R _invR
    int lim=2;
    R[0]=quickpow(f[0]);
    while(lim<n<<1){
        for(register int i=0;i<lim;++i)_R[i]=R[i],R[i]=f[i];
        for(register int i=0;i<lim<<1;++i)tr[i]=(tr[i>>1]>>1)|(i&1?lim:0);
        NTT(_R,lim<<1,0),NTT(R,lim<<1,0);
        for(register int i=0;i<lim<<1;++i)R[i]=1ll*qm(2+mod-1ll*_R[i]*R[i]%mod)*_R[i]%mod;
        NTT(R,lim<<1,1),lim<<=1;
        for(register int i=lim>>1;i<lim;++i)R[i]=0;
    }
    for(register int i=0;i<n;++i)g[i]=R[i];
    for(register int i=0;i<lim;++i)R[i]=_R[i]=0;
#undef R
#undef _R
}

求导&积分

众所周知，$(x^\mu)’=\mu x^{\mu-1}$。

众所周知，求导逆回去就是积分。

void derivate(int *f,int *g,int n){//对n项多项式f求导，结果存在g中
    for(register int i=1;i<n;++i)g[i-1]=1ll*f[i]*i%mod;
    g[n-1]=0;
}
void intergrate(int *f,int *g,int n){//积分，同上
    for(register int i=n;i;--i)g[i]=1ll*f[i-1]*quickpow(i);
    g[0]=0;
}

ln

给定多项式$A$，求出多项式$B=\ln A$。

众所周知，$\ln’(x)=\dfrac{1}{x}$。于是考虑求导。

但$\ln A$实际上是复合函数求导，要用链式法则$(f(g(x)))’=f’(g(x))g’(x)$。

$B=\ln A$

$B’=\ln’A\times A’$

$B’=A^{-1}A’$

$B=\int(A^{-1}A’)$

求逆+求导+乘法+积分就好了。

int lnR[maxn];
void ln(int *f,int *g,int n){//对n项多项式f求ln，结果存在g中
#define R lnR
    inv(f,R,n),derivate(f,g,n),mul(R,g,g,n,n),intergrate(g,g,n);
    for(register int i=0;i<n;++i)R[i]=0;
#undef R
}

exp

给出$F$，求$G$满足$e^F\equiv G\pmod{x^n}$

倍增+牛顿迭代。

两边取个$\ln$：

$F\equiv \ln G$

$\ln G-F\equiv 0$

令$H(G(x))\equiv \ln G-F$

$H’(G(x))\equiv \dfrac{1}{G}$

套公式：$G\equiv G^*(x)-G^*(\ln G^*-F)\pmod{x^n}$

$G\equiv G^*(1-\ln G^*+F)\pmod{x^n}$

复杂度$O(n\log n)$

int expR[maxn],_expR[maxn];
void Exp(int *f,int *g,int n){//对n项多项式f做exp，结果存在g中
#define R expR
#define _R _expR
    int lim=2;
    R[0]=1;
    while(lim<n<<1){
        for(register int i=0;i<lim;++i)_R[i]=R[i];
        ln(_R,_R,lim);
        for(register int i=1;i<lim;++i)_R[i]=qm(f[i]+mod-_R[i]);
        _R[0]=1,mul(_R,R,R,lim,lim),lim<<=1;
    }
    for(register int i=0;i<n;++i)g[i]=R[i];
    for(register int i=0;i<lim;++i)R[i]=_R[i]=0;
#undef R
#undef _R
}

开根

已知多项式$F$，求出$G$满足$G^2\equiv F\pmod {x^n}$。

最暴力的方法：根据小学数学$\ln x^k=k\ln x$，先把$F\ln$过去，除个$2$再$exp$回来。这样常数较大，但可以开任意$k$次根。

而对于开平方根，同样可以倍增求解。

当多项式只有常数项时，解为常数项模$p$意义下的二次剩余。模板里保证常数项为$1$，解为$1$。

先用牛顿迭代试试：

$G^2-F\equiv 0\pmod{x^n}$

令$H(G(x))\equiv G^2(x)-F(x)$

$H’(G(x))\equiv 2G(x)$

公式套一套：$G(x)\equiv G^*(x)-\dfrac{G^{*2}(x)-F(x)}{2G^*(x)}\pmod{x^n}$

$G^*(x)\equiv \dfrac{F(x)+G^{*2}(x)}{2G^*(x)}\pmod{x^n}$

再试试平方法：

现在已知$R’^2\equiv F\pmod {x^{\frac{n}{2}}}$，要求$R^2\equiv F\pmod {x^n}$

还是根据$R\equiv R’\pmod {x^{\frac{n}{2}}}$

移项平方后得到：

$R^2-2RR’+R’^2\equiv 0\pmod {x^n}$

$F-2RR’+R’^2\equiv 0\pmod{x^n}$

$R=\dfrac{F+R’^2}{2R’}\pmod{x^n}$

套个多项式求逆即可，复杂度$O(n\log n)$。

const int inv2 = quickpow(2);
int sqrtR[maxn],_sqrtR[maxn],tem[maxn];
void Sqrt(int *f,int *g,int n){//对项数为n的多项式f开根，结果存在g里
#define R sqrtR
#define _R _sqrtR
    int lim=2;
    R[0]=1;
    while(lim<n<<1){
        for(register int i=0;i<lim;++i)tem[i]=f[i],_R[i]=R[i];
        inv(R,R,lim);
        for(register int i=0;i<lim<<1;++i)tr[i]=(tr[i>>1]>>1)|(i&1?lim:0);
        NTT(R,lim<<1,0),NTT(tem,lim<<1,0);
        for(register int i=0;i<lim<<1;++i)R[i]=1ll*R[i]*tem[i]%mod;
        NTT(R,lim<<1,1);
        for(register int i=0;i<lim;++i)R[i]=1ll*qm(R[i]+_R[i])*inv2%mod;
        lim<<=1;
        for(register int i=lim>>1;i<lim;++i)R[i]=0;
    }
    for(register int i=0;i<n;++i)g[i]=R[i];
    for(register int i=0;i<lim;++i)R[i]=_R[i]=tem[i]=0;
#undef R
#undef _R
}

快速幂

快速幂好说，直接$A^k=\exp(k\ln A)=\exp((k\bmod p)\ln A)$。

$\ln+\exp$即可，常数很大。

也可以直接倍增快速幂，看上面的式子发现$k$可以对$p$（不是$p-1$）取模，$O(n\log^2 n)$暴力乘法。

void Pow(int *f,int *g,int n,int k){//f^k
    ln(f,g,n);
    for(register int i=0;i<n;++i)g[i]=1ll*g[i]*k%mod;
    Exp(g,g,n);
}

带余除法

给定$n$项多项式$A(x)$和$m$项多项式$B(x)$，求出$n-m+1$项多项式$F(x)$和$m-1$次多项式$G(x)$，使得$A=B\times F+G$。

把$x$都换成$x^{-1}$，显然还是相等的。

$A(x^{-1})=B(x^{-1})F(x^{-1})+G(x^{-1})$

两边同乘$x^n$：

$x^nA(x^{-1})=x^nB(x^{-1})F(x^{-1})+x^nG(x^{-1})$

考虑一个$n$项多项式$A(x)$，$x^nA(x^{-1})$相当于是把$A$的系数翻转了一下，以下记为$A^R(x)$。

$A^R(x)=B^R(x)F^R(x)+x^{n-m+1}G^R(x)$

看到后面那个$x^{n-m+1}$，直接强制$\bmod {x^{n-m+1}}$消掉它。

$A^R(x)\equiv B^R(x)F^R(x)\pmod{x^{n-m+1}}$

求逆再翻转回来就能得到$F(x)$，然后根据最原始的式子$A=B\times F+G$就能得到$G$。

int divR[maxn],divF[maxn],divG[maxn];
void div(int *f,int *g,int n,int m,int *d,int *mo){//f=d*g+mo
#define R divR
#define F divF
#define G divG
    for(register int i=0;i<n;++i)F[i]=f[n-i-1];
    for(register int i=0;i<m;++i)G[i]=g[m-i-1];
    inv(G,R,n-m+1),mul(R,F,R,n-m+1,n-m+1);
    reverse(F,F+n),reverse(G,G+n),reverse(R,R+n);
    for(register int i=0;i<=n-m;++i)d[i]=R[i];
    mul(R,G,R,n,n);
    for(register int i=0;i<m;++i)mo[i]=qm(F[i]+mod-R[i]);
    for(register int i=0;i<n;++i)F[i]=G[i]=R[i]=0;
#undef R
#undef F
#undef G
}

任意模数NTT

咕咕咕

分治FFT

咕咕咕

三角函数

咕咕咕咕咕咕咕咕咕

生成函数

初来乍到，多多包涵。

引入

假设你在看cxk的视频。同时你有一个愉♀悦度。已知：

看cxk唱歌可以增加1点愉♀悦度

看cxk跳舞可以增加2点愉♀悦度

看cxk说rap可以增加3点愉♀悦度

看cxk打篮球可以增加4点愉♀悦度

重复看每种视频只能增加一次愉♀悦度。对于$n\in[1,10]$，有多少种看视频的方案能使愉♀悦度达到恰好$n$？

显然，这个问题可以用背包轻松解决。

考虑另一种奇妙的做法。对每种方式，构造一个形如$\sum\limits_{i=0}^\infty a_ix^i$多项式代表它。其中$x$的指数代表一个状态，这里表示愉♀悦度；$a_i$表示达到这种状态的方案数；而$x$本身没有意义，只是一个载体。

以唱歌为例构造多项式：有两种选择：看cxk唱歌或不看。这就分别代表了$1x^1$和$1x^0$。所以唱歌的多项式为$1+x$

类似的，跳舞的多项式为$1+x^2$，rap为$1+x^3$，打篮球为$1+x^4$。

那么将两个多项式相乘会发生什么？

考虑一个多项式的某一项$a_ix^i$和另一个多项式的某一项$a_jx^j$的贡献，指数$i,j$相加，表示了状态$i+j$；系数$a_i,a_j$相乘，是乘法原理，即达到状态$i+j$的方案数；而每一个$x^{i+j}$的系数$a_ia_j$加起来，又是加法原理。最终得到的新多项式就是用这两种方式的方案情况！

所以，将$4$个多项式乘起来，取$n$次项就是答案。

定义

对一个数列$\{a_i\}$，其普通生成函数（$OGF$）为$\sum\limits_{i=0}^\infty a_ix^i$，指数生成函数（$EGF$）为$\sum\limits_{i=0}^\infty \dfrac{a_i}{i!}x^i$。

比如说数列$\{1,1,1,1…\}$的生成函数为$\sum\limits_{i=0}^\infty x^i$。

我们发现这其实是一个等比数列求和，等于$\dfrac{1-x^\infty}{1-x}$。根据引入部分，这个$x$其实没啥意义。如果给$x$代一个$(-1,1)$的数，$x^\infty$趋近于$0$，这个式子就为$\dfrac{1}{1-x}$。

普通生成函数，一般用于无标号计数问题。而指数生成函数一般用于有标号计数问题。这个很好理解，因为有标号的除以$n!$就成为无标号问题了。

一些常见的生成函数：

$\sum\limits_{n=0}^\infty ax^n=\dfrac{a}{1-x}$
$\sum\limits_{n=0}^\infty x^{dn}=\dfrac{1}{1-x^d}$
$\sum\limits_{n=0}^\infty c^nx^n=\dfrac{1}{1-cx}$
$\sum\limits_{n=0}^\infty C_k^nx^n=(x+1)^k$
$\sum\limits_{n=0}^\infty C_{n+k-1}^{k-1}x^n=\dfrac{1}{(1-x)^k}$。（广义二项式定理）
$\sum\limits_{n=0}^\infty \dfrac{c^nx^n}{n!}=e^{cx}$（泰勒公式）
$\sum\limits_{n=1}^\infty \dfrac{c^nx^{dn}}{n}=\ln\left(\dfrac{1}{1-cx^d}\right)$

应用

推导通项公式

序

有$k$个非负变量$x_i$，求满足$\sum\limits_{i=1}^kx_i=n$的方案数。

考虑生成函数做法，因为$x_i\in[0,n]$，所以它对应的数列就是$\{1,1,1\dots\}$，构造生成函数$\sum\limits_{i=0}^nx^i=\dfrac{1}{1-x}$，乘$k$次就是每个$n$的方案数的生成函数，即$\dfrac{1}{(1-x)^k}$。

我们只要找出这个生成函数对应数列就能知道答案。

根据前文，$\dfrac{1}{(1-x)^k}=\sum\limits_{i=0}^\infty C_{i+k-1}^{k-1}x^i$。

于是得到答案为$C_{n+k-1}^{k-1}$。实际上这和插板法得到的是一样的。

简单的例题

直接根据题意构造$10$个生成函数就好了：

$6$的倍数：$\sum\limits_{n=0}^\infty[6|n]x^n=\dfrac{1}{1-x^6}$
最多用$9$块：$\sum\limits_{n=0}^9 x^n=\dfrac{1-x^{10}}{1-x}$
$\dots$

把这些乘起来，化简得到$\dfrac{1}{(1-x)^5}$。再把这个生成函数还原成数列。

$\dfrac{1}{(1-x)^5}=\sum\limits_{n=0}^\infty C_{n+4}^4x^n$

第$n$项就是答案，即$C_{n+4}^4=\dfrac{(n+1)(n+2)(n+3)(n+4)}{24}$。

只要套个高精就行了事实上不久之前这个题缩短时限把python卡掉了，涉及到100000位的高精乘高精你还要写个FFT/NTT

斐波那契数列通项公式

上面这些没啥意思，我们试试用生成函数推导斐波那契数列的通项公式。

定义斐波那契数列$fib_0=0,fib_1=1,fib_i=fib_{i-1}+fib_{i-2}$。

令$\{fib_n\}$的$OGF$为$F(x)=\sum\limits_{n=0}^\infty fib_nx^n$.

根据斐波那契数列的递推式，可以考虑错位相减法。乘上$x$就能使数列平移一位。

$\ \ \ F(x)=fib_1x^1+fib_2x^2+fib_3x^3\dots$

$\ xF(x)=0\qquad\ +fib_1x^2+fib_2x^3\dots$

$x^2F(x)=0\qquad\ +0\qquad\ +fib_1x^3\dots$

我们发现$F(x)$和$xF(x)+x^2F(x)$只差了个$fib_1x=x$。

于是$F=x+xF+x^2F$，即$F=\dfrac{x}{1-x-x^2}$。

这玩意看不透它的数列，考虑转化为常见的形式：

设$\dfrac{x}{1-x-x^2}=\dfrac{A}{1-ax}+\dfrac{B}{1-bx}$

相加肯定是要通分的，看分母，有$1-x-x^2=(1-ax)(1-bx)=abx^2-(a+b)x+1$

系数分别相同，有$\begin{cases}ab=-1\\a+b=1\end{cases}$

解得$a=\dfrac{1+\sqrt5}{2},b=\dfrac{1-\sqrt5}{2}$。

代回去看分子：$A(1-bx)+B(1-ax)=A+B-\dfrac{(1-\sqrt5)Ax}{2}-\dfrac{(1+\sqrt5)Bx}{2}=x$

还是看相同的系数，得出$\begin{cases}A+B=0\\ -\dfrac{(1-\sqrt5)A}{2}-\dfrac{(1+\sqrt5)B}{2}=1\end{cases}$

解得$A=\dfrac{1}{\sqrt5},B=-\dfrac{1}{\sqrt5}$

回到最初的目的，$\dfrac{x}{1-x-x^2}=\dfrac{1}{\sqrt5}\left[\dfrac{1}{1-(\frac{1+\sqrt5}{2})x}-\dfrac{1}{1-(\frac{1-\sqrt5}{2})x}\right]$

我们知道，$\dfrac{1}{1-ax}=\sum\limits_{n=0}^\infty a^nx^n$

于是斐波那契数列生成函数为$\sum\limits_{n=0}^\infty\frac{1}{\sqrt5}\left[(\frac{1+\sqrt5}{2})^n-(\frac{1-\sqrt5}{2})^n\right]x^n$

就能得到$fib_n=\frac{1}{\sqrt5}\left[(\frac{1+\sqrt5}{2})^n-(\frac{1-\sqrt5}{2})^n\right]$

卡特兰数通项公式

我不是鸽子！我来抄推卡特兰数通项辣！

卡特兰数的定义式为$c_0=1,c_n=\sum\limits_{i=0}^{n-1}c_ic_{n-1-i}$。看起来很卷积。

令$F(x)$为$\{c_n\}$的生成函数。

$F=\sum\limits_{n=0}^\infty c_nx^n$

$=\sum\limits_{n=0}^\infty x^n\left([n=0]+\sum\limits_{i=1}^{n-1}c_ic_{n-1-i}\right)$

$=1+xF^2$

解一元二次方程，$F=\dfrac{1\pm\sqrt{1-4x}}{2x}$

诶？这咋有个$\pm$啊？

$F$当然不会有两个解，要舍掉一个。

虽然生成函数中$x$本身没有意义，但是给它代个值是可以的。比如$0$就很好，因为$F(0)$就是常数项。

而本题中$F(0)=1$，取加号时等式右边为$\dfrac{2}{0}=+\infty$，取减号时为$\dfrac{0}{0}=1$，舍掉加号。

所以$F(x)=\dfrac{1-\sqrt{1-4x}}{2x}$

然后开始抄~~rqy~~铃悬的博客：

根据广义二项式定理展开$\sqrt{1-4x}$

$(1-4x)^{\frac{1}{2}}$

$=\sum\limits_{n=0}^\infty C_{\frac{1}{2}}^n(-4x)^n$

$=1+\sum\limits_{n=1}^\infty\dfrac{\frac{1}{2}(-\frac{1}{2})(-\frac{3}{2})\dots(\frac{3}{2}-n)}{n!}(-4x)^n$

$=1+\sum\limits_{n=1}^\infty\dfrac{(-1)(-3)\dots(3-2n)}{n!}(-2x)^n$

$=1-\sum\limits_{n=1}^\infty\dfrac{1\times3\times\dots(2n-3)}{n!}(2x)^n$

$=1-\sum\limits_{n=1}^\infty\dfrac{1\times2\times 3\times4\times\dots(2n-3)\times(2n-2)}{2\times4\times\dots(2n-2)n!}(2x)^n$

$=1-\sum\limits_{n=1}^\infty\dfrac{(2n-2)!}{1\times2\times\dots(n-1)n!}2x^n$

$=1-\sum\limits_{n=1}^\infty\dfrac{(2n-2)!}{(n-1)!n!}2x^n$

把它代回去：

$F(x)=\dfrac{1-\sqrt{1-4x}}{2x}$

$=\dfrac{\sum\limits_{n=1}^\infty\dfrac{(2n-2)!}{(n-1)!n!}2x^n}{2x}$

$=\sum\limits_{n=1}^\infty\dfrac{(2n-2)!}{n!(n-1)!}x^{n-1}$

$=\sum\limits_{n=0}^\infty\dfrac{(2n)!}{(n+1)!n!}x^n$

$=\sum\limits_{n=0}^\infty\dfrac{C_{2n}^n}{n+1}x^n$

于是得出卡特兰数通项公式为$c_n=\dfrac{C_{2n}^n}{n+1}$

结合多项式

例题

设$f(n)$为权值为$n$的神犇二叉树数量。

枚举根、左右儿子的权值，$f(0)=1,f(n)=\sum\limits_{i=1}^n[i\in C]\sum\limits_{j=0}^{n-i}f(j)f(n-i-j)$

后面那个看起来很卷积很多项式。

令$\{a_n=[n\in C]\}$的$OGF$为$G(x)=\sum\limits_{n=0}^\infty[n\in C]x^n$，$\{f(n)\}$的$OGF$为$F(x)\sum\limits_{n=0}^\infty f(n)x^n$

$F(x)=\sum\limits_{n=0}^\infty x^n\left([n=0]+\sum\limits_{i=1}^n[i\in C]\sum\limits_{j=0}^{n-i}f(i)f(n-i-j)\right)$

于是有$F=1+GF^2$。

解这个一元二次方程得$F=\dfrac{1\pm\sqrt{1-4G}}{2G}$。

$G(0)=0,F(0)=1$，令$x=0$，计算可知取减号。

$F=\dfrac{1-\sqrt{1-4G}}{2G}$。这就是个多项式问题了。直接上板子。

但是当你兴冲冲地默写完多项式开根和求逆后会懵逼地发现：由于$G(0)=0$，$2G$求逆后全变成$0$了！

这咋整啊？分母无理化呗！

分式上下同乘$1+\sqrt{1-4G}$得：$F=\dfrac{1-(1-4G)}{2G(1+\sqrt{1-4G})}=\dfrac{2}{1+\sqrt{1-4G}}$

这样就可以做了。

水题

整数的lqp拆分

设$f(n)$为答案。

~~根据打表可知f(n)=2f(n-1)+f(n-2)，高精矩乘应该能过~~

显然有$f(0)=1,f(n)=\sum\limits_{i=1}^nfib(i)f(n-i)$

设$\{fib(i)\}$的$OGF$为$G(x)=\sum\limits_{n=0}^\infty fib(n)x^n$（不要在意为什么是$G$），$\{f(i)\}$的$OGF$为$F(x)=\sum\limits_{n=0}^\infty f(n)x^n$

$F(x)=\sum\limits_{n=0}^\infty x^n\left([n=0]+\sum\limits_{i=1}^nfib(i)f(n-i)\right)$

$F=1+F\times G$

$F=\dfrac{1}{1-G}$

根据前文，$G(x)=\dfrac{x}{1-x-x^2}$

$F=\dfrac{1}{1-\frac{x}{1-x-x^2}}=\dfrac{1-x-x^2}{1-2x-x^2}=1+\dfrac{x}{1-2x-x^2}$

和斐波那契数列通项的推导类似，设$\dfrac{1}{1-2x-x^2}=\dfrac{A}{1-ax}+\dfrac{B}{1-bx}$

解方程就不说了，最终解得$a=1+\sqrt2,b=1-\sqrt2,A=\dfrac{1}{2\sqrt2},B=-\dfrac{1}{2\sqrt2}$

得出通项为$f(n)=\dfrac{\sqrt2}{4}[(1+\sqrt2)^n-(1-\sqrt2)^n]$

不会二次剩余？$O(p)$枚举得出$59713600^2\equiv2\pmod{10^9+7}$

城市规划

$EGF$结合多项式。

题解

付公主的背包

生成函数与多项式$\ln$和$\exp$的应用。

题解

ZJL的妹子序列

一句话题意：求恰好有$k$对逆序对的$1\sim n$排列数。$n,k\le 10^5$。

和「付公主的背包」挺像的。设$f(i,j)$为恰有$j$对逆序对的$1\sim i$排列数。

$f(i,0)=1,f(i,j)=\sum\limits_{k=0}^{i-1}f(i-1,j-k)$

令$\{f(i)\}$的普通生成函数为$F_i(x)$。

$F_i=\sum\limits_{n=0}^\infty f(i,n)x^n$

$=\sum\limits_{n=0}^\infty x^n\sum\limits_{j=0}^{i-1}f(i-1,n-j)$

$=\sum\limits_{j=0}^{i-1}x^jF_{i-1}$

$\dfrac{F_i}{F_{i-1}}=\dfrac{1-x^i}{1-x}$

累乘得到$F_n=F_0\prod\limits_{i=1}^n\dfrac{1-x^i}{1-x}$

$F_0=1$就不要了。还是通过取对数转乘为加：

$F_n=\exp\sum\limits_{i=1}^n\ln\dfrac{1-x^i}{1-x}$

$=\exp\sum\limits_{i=1}^n\left(\ln\dfrac{1}{1-x}-\ln\dfrac{1}{1-x^i}\right)$

$=\exp\sum\limits_{i=1}^n\left(\sum\limits_{k=1}^\infty\dfrac{x^k}{k}-\sum\limits_{k=1}^\infty\dfrac{x^{ik}}{k}\right)$

$=\exp\left(\sum\limits_{k=1}^\infty\dfrac{n}{k}x^k-\sum\limits_{i=1}^n\sum\limits_{k=1}^\infty\dfrac{x^{ik}}{k}\right)$

枚举倍数构造多项式再$\exp$回来即可，$O(n\log k)$的。

射命丸文的笔记

和「城市规划」差不多。

题解

玩游戏

答案为$\dfrac{\sum\limits_{i=1}^n\sum\limits_{j=1}^m(a_i+b_j)^k}{nm}$，只考虑分子。

用二项式定理展开：

$\sum\limits_{i=1}^n\sum\limits_{j=1}^m(a_i+b_j)^k$

$=\sum\limits_{x=0}^k\sum\limits_{i=1}^n\sum\limits_{j=1}^mC_k^xa_i^xb_i^{k-x}$

$=k!\sum\limits_{x=0}^k\dfrac{\sum\limits_{i=1}^na_i^x}{x!}\dfrac{\sum\limits_{j=1}^mb_j^{k-x}}{(k-x)!}$

搞出来$3$个$EGF$卷一下就好了，问题是怎么求$\sum\limits_{i=1}^na_i^k$。

先把$\{a_i^k\}$写成生成函数：$\sum\limits_{k=1}^\infty a_i^kx^k=\dfrac{1}{1-a_ix}$。

那么$\left\{\sum\limits_{i=1}^na_i^k\right\}$的生成函数$F(x)$就是这$n$个生成函数的和，即$F(x)=\sum\limits_{i=1}^n\dfrac{1}{1-a_ix}$。

令$G(x)=\sum\limits_{i=1}^n\dfrac{-a_i}{1-a_ix}$。

接下来变魔术：

$F(x)=n+\sum\limits_{i=1}^n\dfrac{1-1+a_ix}{1-a_ix}=-xG(x)+n$

现在要求$G(x)$。发现$\ln’(1-a_ix)=\dfrac{-a_i}{1-a_ix}$。

于是$G(x)=\sum\limits_{i=1}^n\ln’(1-a_ix)=\ln’\left(\prod\limits_{i=1}^n(1-a_ix)\right)=\dfrac{\left(\prod\limits_{i=1}^n(1-a_ix)\right)’}{\prod\limits_{i=1}^n(1-a_ix)}$

这个连乘用分治求。将两边区间的结果$NTT$乘起来。复杂度为$T(n)=2T(\frac{n}{2})+O(n\log n)=O(n\log^2n)$。最后还原上面的推导。

终于做完了。。。

~~然后发现我是真的真的真的写不动，那就光嘴巴好了~~

概率论

题解

多项式全家桶&生成函数学习笔记

前言