CF1264D1 题解

标签：后缀 题解 texttt CF1264D1 序列 text 数量 check

blog。写一个题解区没有的蠢做法，不依赖 dp 但是很难转到 Hard Version（

---

对于已经确定的序列，深度有单调性。就是如果答案为 \(x\)，那么肯定能选出深度为 \(1\sim x\) 的子序列。

记 \(\operatorname{check}_s(x)\) 表示 check 序列 \(s\) 能否选出深度为 \(x\) 的子序列。考虑如何 check：

• 发现形如 \(\texttt{((}\cdots\texttt{(())}\cdots\texttt{))}\) 的结构最优。
• 记 \(pre_i\) 表示 \([1,i]\) 中 ( 的数量，\(suf_i\) 表示 \([i,n]\) 中 ) 的数量，只需满足：\(\exists\min(pre_i,suf_{i+1})\ge x\)。
• 找到序列第一个 \(pre_i=x\) 的位置，检验是否有 \(suf_{i+1}\ge x\) 即可。

显然，对于确定序列有 \(\text{ans}_s=\sum\limits_{x=1}^n \operatorname{check}_s(x)\)。

回到原问题，枚举 \(x=1\sim n\)，权值和转为了计数：只需计数 \(\operatorname{check}_s(x)=1\) 的 \(s\) 数量，所有 \(x\) 的方案数加起来就行！

最后将上述 \(\operatorname{check}_s(x)\) 的过程放到计数上就行：

• 枚举 \(i\)，这个 \(i\) 需要满足：是序列第一个 \(pre_i=x\) 的位置，且有 \(suf_{i+1}\ge x\)。
• 若 \(s_i=\texttt{(}\)，前半段在 \(\texttt{?}\) 中凑够左括号数就行，后半段在 \(\texttt{?}\) 中凑到 \(\ge x\) 就行。有贡献：

\[\binom{\text{前缀 }\texttt{?}\text{ 的数量}}{x-\text{前缀 }\texttt{(}\text{ 的数量}}\times\sum\limits_{x-\text{后缀 }\texttt{)}\text{ 的数量}}^{\text{后缀 }\texttt{?}\text{ 的数量}}\binom{\text{后缀 }\texttt{?}\text{ 的数量}}{i} \]

• 若 \(s_i=\texttt{(}\)，前半段稍微改改就行，有贡献

\[\binom{\text{前缀 }\texttt{?}\text{ 的数量}-1}{x-\text{前缀 }\texttt{(}\text{ 的数量}-1}\times\sum\limits_{x-\text{后缀 }\texttt{)}\text{ 的数量}}^{\text{后缀 }\texttt{?}\text{ 的数量}}\binom{\text{后缀 }\texttt{?}\text{ 的数量}}{i} \]

后面 Sigma 的部分可以预处理，然后枚举 \(x,i\) 后就能 \(O(1)\) 计算。

code，时间复杂度 \(O(n^2)\)。

标签：后缀,题解,texttt,CF1264D1,序列,text,数量,check
From： https://www.cnblogs.com/liangbowen/p/18371843