前言
建议大家看一下我对于 D1 的题解（传送门）后再看本题解，本题解是基于那篇题解的基础上书写的。
数学符号约定
\(\dbinom{n}{m}\)：表示 \(n\) 选 \(m\) 。
如非特殊说明，将会按照上述约定书写符号。
题目分析
首先引用一下 D1 的答案：\(\displaystyle\sum_{i=1}^n\displaystyle\sum_{j=0}^n j\dbinom {s_2}{j-s_1} \dbinom{s_4}{j-s_3}\)
我相信你已经看我我关于 D1 的题解了，现在考虑对那个做法进行优化。
观察一下，发现里面的和式看起来比较好欺负一点，于是考虑优化 \(\displaystyle\sum_{j=0}^n j\dbinom {s_2}{j-s_1} \dbinom{s_4}{j-s_3}\)。
我们先拆一下：
\[\begin{aligned} &\sum_{j=0}^{n} j\dbinom {s_2}{j-s_1} \dbinom{s_4}{j-s_3}\\ =&\sum_{j=0}^{n} (j-s_1+s_1) \dbinom {s_2}{j-s_1} \dbinom{s_4}{j-s_3}\\ =&\sum_{j=0}^{n} (j-s_1) \dbinom {s_2}{j-s_1} \dbinom{s_4}{j-s_3} + \sum_{j=0}^{n} s_1 \dbinom {s_2}{j-s_1} \dbinom{s_4}{j-s_3}\\ =&\sum_{j=0}^{n} (j-s_1) \dbinom {s_2}{j-s_1} \dbinom{s_4}{j-s_3} + s_1\sum_{j=0}^{n} \dbinom {s_2}{j-s_1} \dbinom{s_4}{j-s_3} \end{aligned} \]考虑前面的：
\[\begin{aligned} &\sum_{j=0}^{n} (j-s_1) \dbinom {s_2}{j-s_1} \dbinom{s_4}{j-s_3}\\ =&\sum_{j=0}^{n} (j-s_1) \frac {s_2}{j-s_1} \dbinom {s_2-1}{j-s_1-1} \dbinom{s_4}{j-s_3}\\ =&s_2 \sum_{j=0}^{n} \dbinom {s_2-1}{j-s_1-1} \dbinom{s_4}{s_4+s_3-j}\\ \end{aligned} \]考虑一下 \(\displaystyle\sum_{j=0}^{n} \dbinom {s_2-1}{j-s_1-1} \dbinom{s_4}{s_4+s_3-j}\) 的组合意义，可以得出：
\[\sum_{j=0}^{n} \dbinom {s_2-1}{j-s_1-1} \dbinom{s_4}{s_4+s_3-j} = \dbinom{s_2+s_4-1}{s_4-s_1+s_3-1} \]于是原式变成：
\[s_2\dbinom{s_2+s_4-1}{s_4-s_1+s_3-1} \]现在再考虑后面的：
\[\begin{aligned} &s_1\sum_{j=0}^{n} \dbinom {s_2}{j-s_1} \dbinom{s_4}{j-s_3}\\ =&s_1\sum_{j=0}^{n} \dbinom {s_2}{j-s_1} \dbinom{s_4}{s_4+s_3-j}\\ =&s_1\dbinom{s_2+s_4}{s_4+s_3-s_1} \end{aligned} \]故最后答案变成：
\[\sum_{i=1}^n\sum_{j=0}^n j\dbinom {s_2}{j-s_1} \dbinom{s_4}{j-s_3} = \sum_{i=1}^n s_2\dbinom{s_2+s_4-1}{s_4-s_1+s_3-1}+s_1\dbinom{s_2+s_4}{s_4+s_3-s_1} \]发现可以 \(\mathcal O (n)\) 求解。
注意事项参见 D1 的题解。
代码实现
这里给出了关键部分的代码实现，其余部分还恳请读者自己完成：
// sum1 表示 `(` 数量的前缀和
// sum2 表示 `)` 数量的前缀和
// sum3 表示 `?` 数量的前缀和
int ans = 0;
for (int i = 1; i <= n; i++) {
int s1 = sum1[i];
int s2 = sum3[i];
int s3 = sum2[n] - sum2[i];
int s4 = sum3[n] - sum3[i];
ans = add(ans, mul(s1, C(s2 + s4, s4 + s3 - s1)));
ans = add(ans, mul(s2, C(s2 + s4 - 1, s4 + s3 - s1 - 1)));
}
cout << ans << endl;