「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}](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}](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)\) 再得到最终答案即可