CF1264D2 Beautiful Bracket Sequence

标签：Beautiful 分界点 sum 想不到 括号 Bracket 答案 binom CF1264D2

第二次听这道题，写个推导过程。

考虑对于给定的括号序列如何算答案，考虑最终答案对应回原序列的位置，于是我们要找到一个位置让其左边的左括号与右边的右括号一样多。因为挪指针时两者之一一定变化，并且两边均单调，所以这个分界点是唯一的。

考虑枚举分界点算答案。假设左边有 \(x\) 个问号，右边有 \(y\) 个问号，左边有 \(a\) 个 (，右边有 \(b\) 个 )，枚举答案，则式子形如

\[\begin{aligned} & \sum_{i=0}^n (a+i) \binom{x}{i} \binom{y}{a+i-b} \\ = & a\sum_{i=0}^n \binom{x}{i} \binom{y}{a+i-b} + \sum_{i=0}^n i \binom{x}{i} \binom{y}{a+i-b} \\ = & a\sum_{i=0}^n \binom{x}{i} \binom{y}{y-a+b-i} + \sum_{i=0}^n x \binom{x - 1}{i - 1} \binom{y}{y-a+b-i} \\ = & a \binom{x+y}{y-a+b} + x\binom{x+y-1}{y-a+b-1} \end{aligned} \]

直接算就行了。

感觉和 D1 差不多难，或者说，前面的转化难于后面的推式子，所以感觉没有黑，但有 *2900。感觉好自然，想不到，还是我的问题吗？

可能分界点唯一这个地方是关键，这让拆贡献成为可能。我想到这一步了吗？好像第一次听这道题时第一步都没想到。

下次还是应该写一些自己有一定思考的题，不然连自己为什么想不到到想不到。

新系列：每日拷打自己为什么想不到简单题。

标签：Beautiful,分界点,sum,想不到,括号,Bracket,答案,binom,CF1264D2
From： https://www.cnblogs.com/purplevine/p/solution-cf1264d2.html