自动搬运

查看原文

来自洛谷，原作者为

	csyakuoi 不到普及三等的水平，超越国际金牌的野心。

搬运于2025-08-24 21:47:36，当前版本为作者最后更新于2020-12-03 15:38:56，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

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

经本地测试，$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)$常数奇大无比。