组合数学
假设当前枚举到了位置$i$
$a$ : $i$之前的$($
$b$ : $i$之后的$)$
$c$ : $i$之前的$?$
$d$ : $i$之后的$?$
那么当前位置对于答案的贡献是
$$\sum{a + i \leqslant b + j}{\tbinom{c}{i} \tbinom{d}{j}}$$
这里的i和j分别表示填了$i$个$($,填了$j$个$)$
这个式子很巧妙，$a + i$ 表示最终答案配对的括号个数，相当于计算了当前这个位置的$($对答案的贡献
然后考虑化简
$$=\sum_{a + i \leqslant b + d - j}{\tbinom{c}{i} \tbinom{d}{d - j}}$$
$$=\sum_{x = 0}^{b + d - a}{\tbinom{c + d}{x}}$$
由于$c + d$只会有两种取值，预处理即可
复杂度$O(n)$
#include <bits/stdc++.h> using namespace std; const int P = 998244353; int main() { string s; cin >> s; int n = s.size(); vector<int> inv(n + 1), facinv(n + 1), fac(n + 1); fac[0] = inv[1] = facinv[0] = 1; for(int i = 1; i <= n; ++i) { if(i != 1) { inv[i] = 1LL * (P - P / i) * inv[P % i] % P; } facinv[i] = 1LL * facinv[i - 1] * inv[i] % P; fac[i] = 1LL * fac[i - 1] * i % P; } int a = 0, b = 0, c = 0, d = 0; for(auto e : s) { if(e == ‘)‘) { ++b; } if(e == ‘?‘) { ++d; } } map<int, vector<int> > dp; auto C = [&] (int n, int m) { if(n < m) return 0; if(dp.find(n) != dp.end()) { return dp[n][m]; } auto &tmp = dp[n]; int sum = 0; tmp.resize(n + 1); for(int i = 0; i <= n; ++i) { sum += 1LL * fac[n] * facinv[i] % P * facinv[n - i] % P; sum %= P; tmp[i] = sum; } return tmp[m]; }; auto calc = [&] (int a, int b, int c, int d) { int x = min(b + d - a, c + d); if(x < 0) return 0; return C(c + d, x); }; int ans = 0; for(int i = 0; i < n; ++i) { if(s[i] == ‘(‘) { ++a; } if(s[i] == ‘)‘) { --b; } if(s[i] == ‘?‘) { ++c; --d; } if(s[i] == ‘(‘) { ans += calc(a, b, c, d); ans %= P; } if(s[i] == ‘?‘) { ++a; --c; ans += calc(a, b, c, d); ans %= P; --a; ++c; } } cout << ans << ‘\n‘; return 0; }
原文：https://www.cnblogs.com/19992147orz/p/12025147.html
