专栏文章

AGC071B

llsj2009Isj2OO9
AT_agc071_b题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@minvipq8
此快照首次捕获于
2025/12/02 09:02
3 个月前
此快照最后确认于
2025/12/02 09:02
3 个月前
查看原文
给定 TT 如何求出 SS？
  1. 选取尽可能多（设选了 kk 个）的 () 直至无解（具体的，不断选取接下来的首个 ( 或 )）。这显然是最优的。删去最后一个 () 之前得所有未在 () 之中的括号。
  2. 从前往后扫一遍 TT，没有匹配上的括号在 SS 中不优：以 ) 为例，若其在 SS 中则前面必然有至少有一个 ) 不在 SS 中，因为现在这个 ) 居然能匹配上，那把这个 ) 在 SS 中删除，前面的 ) 加入 SS 必然不劣。如此 TT 变成一合法括号序列。
  3. 此时需要在 SS 的后缀中选取长为 K−2kK-2k 的字典序最大合法括号序列，且已知答案不可能以 () 开头。则首要目标是最小化前导 ( 个数，我们考虑每次选出一个前导的 ( 与对应的 ) 删除。若该 SS 后缀形如 ((((.).).).)...：
    • 删除最外层的 ( 会得到 (((.).).)....。
    • 删除次外层的 ( 会得到 (((.).)..)...。
    对比下来看，一个合法括号序列肯定是 ( 打头，或者是空串，前者删除次外层更劣后者则没有区别，删除其于非最外层 ( 的结果是类似的。可见应当不断删除最外层 ( 和其对应的 ) 直至 ∣S∣=K−2k|S|=K-2k。
那么倒过来，给定 SS 求出对应的 TT：
  1. 把 SS 写成 aa 个 () 拼上 bb 个最外层合法括号序列（令后者为括号序列 BB）形式。
  2. 不断在 BB 开头插入 (，两个最外层合法括号序列之间插入 )。
  3. 在 BB 的最外层合法括号序列间隔中依次插入一些 ))..)((..(。不在 BB 中插入的原因是会记重，即插入这些括号的地方要真的失配。
  4. 选取一字符串 AA 满足恰好包含了 aa 个不交的 ()，并且最后以 () 结尾。
  5. 最终 T=A+BT=A+B。
对于中间三步分别考虑，写出关于新插入字符数的生成函数，最终取 [xn−K]\left[x^{n-K}\right] 即可：
  1. 设最后面的 ) 插入在了第 ii 个最外层合法括号序列后，答案为 x2(1−x2)i\frac{x^2}{(1-x^2)^i}。特判这一步没有插入任何括号的情况。
  2. 设第 22 步中设最后面的 ) 插入在了第 ii 个最外层合法括号序列后，则此时还有 b−i+1b-i+1 个最外层合法括号序列，先不区分左右括号，最终再划定其分界线，答案为：（共 b−i+2b-i+2 个位置可插括号，插板计算方案数）
∑j≥0(j+1)(j+b−i+1b−i+1)xj=(x∑j≥0(j+b−i+1b−i+1)xj)′=(x(1−x)b−i+2)′=(b−i+1)x+1(1−x)b−i+3\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}
  1. 开头可以插 )，() 间可以插 (，)( 间可以插 )，答案即为 1(1−x)2a\frac{1}{(1-x)^{2a}}。
相乘，求和，方案数为：
[xN−K]∑1≤i≤bx2(1−x2)i(b−i+1)x+1(1−x)b−i+31(1−x)2a=[xN−K]x2(1−x)2a+b+3∑1≤i≤b(b−i+1)x+1(1+x)i\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，可以分别求出：
∑0≤i<b1(1+x)i=1+1x−1x(x+1)b−1∑0≤i<bi(1+x)i=−(1+x)(∑0≤i<b1(1+x)i)′=−(1+x)(1x−1x(x+1)b)′=1x+1x2−bx+1(x+1)b−1\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}
再带回原式：
11+x∑0≤i<b(b−i)x+1(1+x)i=1x+1((bx+1)∑0≤i<b1(1+x)i−x∑0≤i<bi(1+x)i)=1x+1((bx+1)(1+1x−1x(x+1)b−1)−1−1x+bx+1x(x+1)b−1)=b\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}
再加上没有在第二步插入括号的情况，答案即为：
[xN−K]bx−x+1(1−x)2a+b+3=(b−1)(N−K+2a+b+12a+b+2)+(N−K+2a+b+22a+b+2)\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=0b=0 的情况，直接用第四步推得的东西，再在最后插一些任意的括号。总复杂度 O(N)\mathcal{O}(N)。

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...