题解 P3310 【[SDOI2014]括号序列计数】

· · 题解

仅用这篇题解的方法不能通过本题，只是抛砖引玉，同时也是希望让更多人来研究这道题，如果什么时候有人用可以通过的算法发出题解，请管理员将此题解撤下。

经本地测试，n=1的数据可以4秒跑过，n=2需要60秒。

考虑n=1的情况，设f_i表示长度为i的序列的数量，a,b,c分别为左括号，右括号，空格转移边的数量，则：

f_i=cf_{i-1}+ab\sum_{i=0}^{n-2}f_if_{n-2-i}

（先考虑第一个字符是否是空格，如果不是，再考虑与之匹配的右括号的位置）。

发现是一个卷积的形式，于是考虑生成函数（表述不严谨请见谅）。

设F是f的生成函数，则有：

F=abx^2F^2+cxF+1

最后那个1是因为f_0=1。多项式求逆+开根即可，因为模数很小，所以单模NTT就够了。

考虑n=2，设f_i(n)为起始—终止状态为i，长度为n的序列数量，0 \leq i<4，二进制高位表示起始状态，低位表示终止状态。

两段合法括号序列拼起来可以形成新的合法序列，同样是卷积的形式，于是设F_i是f_i的生成函数，则有。

F_i=\sum_{j=0}^3\sum_{k=0}^3H_{i,j,k}F_jF_k+\sum_{j=0}^3G_{i,j}F_j+1(i=0/i=3) F_i=\sum_{j=0}^3\sum_{k=0}^3H_{i,j,k}F_jF_k+\sum_{j=0}^3G_{i,j}F_j(i=1/i=2)

其中G_{i,j}与H_{i,j,k}为已知二次多项式。

不能直接求通项，怎么办？

考虑分治，设：

P_i \equiv F_i(\mod x^n) P_j \equiv F_j(\mod x^n) (P_i-F_i)(P_j-F_j) \equiv 0(\mod x^{2n}) F_iF_j \equiv P_iF_j+P_jF_i-P_iP_j(\mod x^{2n})

把多项式看成参数，高斯消元即可，容易证明，每次消元是分母多项式必然可求逆，时间复杂度O(klogk)常数奇大无比。