重 拳 出 击


前言

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)$。 最后还原上面的推导。

终于做完了。。。

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

概率论

题解