「2020noip模拟题-蒋凌宇」幂

Analysis

计算$x$出现的次数，可以转化为枚举每一个$x$，计算剩余$n-1$个位置合法括号序列个数

因此我们只需要计算合法括号序列个数

定义一个辅助计数：不可分割 的合法括号序列

这样的括号序列，满足：其恰好为$x$，或者序列两端是一对匹配的左右括号

而实际要求的括号序列 的就是这样的 不可分割括号序列 去掉两端的匹配括号

$$\$$

Solution

设$a_n$为长度为$n$的不可分割 的合法括号序列数量

括号序列并非排列问题，因此我们用普通生成函数计算

设$\text{OGF(a)}=A(x)$，$A(x)$容易发现$A(x)$满足下面的递归式

$\displaystyle A(x)=x^2(\sum_{i=0}^{\infty} A^i(x))+x^1$

其中$x^2$表示在外层加一对匹配括号，$\sum_{i=0}^{\infty} A^i(x)$枚举子括号中的分裂段，$x^1$表示单个$x$

容易得到下面的化简过程

$\displaystyle A(x)=\frac{x^2} {1-A(x)}+x$

$A(x)-A^2(x)=x^2+xA(x)$

$A^2(x)-(x+1)A(x)+x^2+x=0$

带入求根公式，得到$A(x)$的 收敛形式

$\displaystyle A_1(x)=\frac{x+1+\sqrt{-3x^2-2x+1} } {2},A_2(x)=\frac{x+1-\sqrt{-3x^2-2x+1} } {2}$

令$\displaystyle F(x)=-3x^2-2x+1,G(x)=\sqrt{F(x)}$

容易手玩发现：$[x^0]G(x)=1$

而根据定义，我们知道$[x^0]A(x)=0$，因此$A(x)=A_2(x)$

接下来我们要求$\displaystyle G(x)=F^\frac{1} {2}(x)$

$$\$$

下面介绍对于短多项式$F(x)$，设$\text{deg}(F(x))=m$，有理数$k(k\ne 1)$

求解$G(x)=F^k(x)$的前$n$项的$O(m^2+nm)$递推做法

变形

$G(x)=F^k(x)$

$\displaystyle G’(x)=kF^{k-1}(x)F’(x)$

$G’(x)F(x)=kF^k(x)F’(x)$

$G’(x)F(x)=kG(x)F’(x)$

$$\$$

求解递推式

对于等号两边，考虑$[x^n]$一项的系数，容易求出$F’(x)=-6x-2$

$\displaystyle \sum_{i=0}^m [x^{n-i}]G’(x)F_i=k\sum_{i=0}^{m-1}[x^{n-i}]G(x)F’_i$

$\displaystyle \sum_{i=0}^m x^{n-i+1}G(x)F_i=k\sum_{i=0}^{m-1}[x^{n-i}]G(x)F’_i$

$\displaystyle (n+1)[x^{n+1}]G(x)=k\sum_{i=0}^{m-1}[x^{n-i}]G(x)F’_i-\sum_{i=1}^m x^{n-i+1}G(x)F_i$

带入这题的$k$，得到

$\displaystyle [x^n]=\frac{3(n-3)[x^{n-2}]+(2n-3)[x^{n-1}]} {n}$

递推边界$[x^0]G(x)=1,[x^1]G(x)=-1$

然后由$G(x)$得到$A(x)$再得到最终答案即可