AGC071B
lsj2009
·
·
题解
给定 T 如何求出 S？
-
选取尽可能多（设选了 k 个）的 () 直至无解（具体的，不断选取接下来的首个 ( 或 )）。这显然是最优的。删去最后一个 () 之前得所有未在 () 之中的括号。
-
从前往后扫一遍 T，没有匹配上的括号在 S 中不优：以 ) 为例，若其在 S 中则前面必然有至少有一个 ) 不在 S 中，因为现在这个 ) 居然能匹配上，那把这个 ) 在 S 中删除，前面的 ) 加入 S 必然不劣。如此 T 变成一合法括号序列。
-
此时需要在 S 的后缀中选取长为 K-2k 的字典序最大合法括号序列，且已知答案不可能以 () 开头。则首要目标是最小化前导 ( 个数，我们考虑每次选出一个前导的 ( 与对应的 ) 删除。若该 S 后缀形如 ((((.).).).)...：
对比下来看，一个合法括号序列肯定是 ( 打头，或者是空串，前者删除次外层更劣后者则没有区别，删除其于非最外层 ( 的结果是类似的。可见应当不断删除最外层 ( 和其对应的 ) 直至 |S|=K-2k。
那么倒过来，给定 S 求出对应的 T：
-
把 S 写成 a 个 () 拼上 b 个最外层合法括号序列（令后者为括号序列 B）形式。
-
不断在 B 开头插入 (，两个最外层合法括号序列之间插入 )。
-
在 B 的最外层合法括号序列间隔中依次插入一些 ))..)((..(。不在 B 中插入的原因是会记重，即插入这些括号的地方要真的失配。
-
选取一字符串 A 满足恰好包含了 a 个不交的 ()，并且最后以 () 结尾。
-
最终 T=A+B。
对于中间三步分别考虑，写出关于新插入字符数的生成函数，最终取 \left[x^{n-K}\right] 即可：
-
设最后面的 ) 插入在了第 i 个最外层合法括号序列后，答案为 \frac{x^2}{(1-x^2)^i}。特判这一步没有插入任何括号的情况。
-
设第 2 步中设最后面的 ) 插入在了第 i 个最外层合法括号序列后，则此时还有 b-i+1 个最外层合法括号序列，先不区分左右括号，最终再划定其分界线，答案为：（共 b-i+2 个位置可插括号，插板计算方案数）
\begin{aligned}
&\sum\limits_{j\ge 0}(j+1)\binom{j+b-i+1}{b-i+1}x^j\\
=&\left(x\sum\limits_{j\ge 0}\binom{j+b-i+1}{b-i+1}x^j\right)'\\
=&\left(\frac{x}{(1-x)^{b-i+2}}\right)'\\
=&\frac{(b-i+1)x+1}{(1-x)^{b-i+3}}
\end{aligned}
- 开头可以插
)，() 间可以插 (，)( 间可以插 )，答案即为 \frac{1}{(1-x)^{2a}}。
相乘，求和，方案数为：
\begin{aligned}
&\left[x^{N-K}\right]\sum\limits_{1\le i\le b}\frac{x^2}{(1-x^2)^i}
\frac{(b-i+1)x+1}{(1-x)^{b-i+3}}\frac{1}{(1-x)^{2a}}\\
=&\left[x^{N-K}\right]\frac{x^2}{(1-x)^{2a+b+3}}
\sum\limits_{1\le i\le b}\frac{(b-i+1)x+1}{(1+x)^i}\\
\end{aligned}
对于后面那个 \sum，可以分别求出：
\begin{aligned}
\sum\limits_{0\le i< b}\frac{1}{(1+x)^i}&=
1+\frac{1}{x}-\frac{1}{x(x+1)^{b-1}}\\
\sum\limits_{0\le i< b}\frac{i}{(1+x)^i}&=
-(1+x)\left(\sum\limits_{0\le i< b}\frac{1}{(1+x)^i}
\right)'\\
&=-(1+x)\left(\frac{1}{x}-\frac{1}{x(x+1)^b}
\right)'\\
&=\frac{1}{x}+\frac{1}{x^2}-\frac{bx+1}{(x+1)^{b-1}}
\end{aligned}
再带回原式：
\begin{aligned}
&\frac{1}{1+x}\sum\limits_{0\le i< b}\frac{(b-i)x+1}{(1+x)^i}\\
=&\frac{1}{x+1}\left((bx+1)\sum\limits_{0\le i<b}\frac{1}{(1+x)^i}
-x\sum\limits_{0\le i<b}\frac{i}{(1+x)^i}\right)\\
=&\frac{1}{x+1}\left((bx+1)\left(1+\frac{1}{x}-\frac{1}{x(x+1)^{b-1}}
\right)-1-\frac{1}{x}+\frac{bx+1}{x(x+1)^{b-1}}\right)\\
=&b
\end{aligned}
再加上没有在第二步插入括号的情况，答案即为：
\begin{aligned}
\left[x^{N-K}\right]\frac{bx-x+1}{(1-x)^{2a+b+3}}=
(b-1)\binom{N-K+2a+b+1}{2a+b+2}+\binom{N-K+2a+b+2}{2a+b+2}
\end{aligned}
还得特判一下 b=0 的情况，直接用第四步推得的东西，再在最后插一些任意的括号。总复杂度 \mathcal{O}(N)。