题意
给定 \(S \in \{ (, ), ? \}\)。
定义深度为括号嵌套的子序列的最大长度除以 \(2\)。
求出将 \(?\) 替换为括号的所有括号串的深度之和，对 \(998244353\) 取模。
\(n \le 10 ^ 6\)。
Sol
考虑如何把每次贡献只计算一次。
不难想到在括号的中心点计算。
可以发现，若当前左右括号的数量不同，可以向左或向右移动到相同的位置。
若中间遇到了右括号，则深度会增大，显然之前的就不是最优的位置了。
设 \(A\) 为前面的 ( 的数量，\(B\) 为后面 ) 的数量。
\(C\) 为前面的 ? 的数量，\(D\) 为后面 ? 的数量。
不难列出 \(n ^ 2\) 的式子（令 \(A > B\)）：
\[\sum_{j = 0} ^ C \dbinom{C}{j} \dbinom{D}{j + A - B} (j + A) \]将括号拆开：
\[A \sum_{j = 0} ^ C \dbinom{C}{C - j} \dbinom{D}{j + A - B} + \sum_{j = 0} ^ C j \dbinom{C}{C - j} \dbinom{D}{j + A - B} \]前面直接范德蒙德卷积/组合意义，对于后面：
\[\sum_{j = 0} ^ C j\frac{C!}{j!(C - j)!} \frac{D!}{(j + A - B)!(D - j + B - A)!} \]把 \(j\) 扔进去，提一个 \(C\) 出来。
\[C \sum_{j = 0} ^ C \frac{(C - 1)!}{(j - 1)!(C - j)!} \frac{D!}{(j + A - B)!(D - j + B - A)!} \]\[C \sum_{j = 0} ^ C \dbinom{C - 1}{C - j} \dbinom{D}{j + A - B} \]类似地，范德蒙德卷积/组合意义。
最终答案为：
\[A \dbinom{C + D}{C + A - B} + C \dbinom{C - 1 + 1}{A - B + C} \]直接 \(O(n)\) 计算即可。
标签：frac,dbinom,NOIP,sum,20240821,T2,括号,数量,德蒙 From： https://www.cnblogs.com/cxqghzj/p/18374829