括号序列的基础处理

• 栈模拟，判断括号序列是否合法，用于多种括号。
• 左括号计数器，用于单种括号。
• 将 ( 看作 1，) 看作 -1。括号序列合法，等价于任意前缀和大于等于 0，且序列元素值和为 0。

AT_abc312_d [ABC312D] Count Bracket Sequences

定义 $f(S)$：将 $S$ 中的所有 ? 换成 ( 或 ) 的合法括号序列数量。给定 $S$，求 $f(S)$。

利用“基础处理 3”中的方法。

设 $f(i, j)$ 代表考虑到下表 $i$，前缀和为 $j$ 的方案数。
根据规则，$j \lt 0$ 的情况不合法，因此我们不考虑。

• 如果 $s_i = \texttt{(}$，则 $f(i-1,j) \to f(i, j + 1)$。
• 如果 $s_i = \texttt{)}$，则 $f(i-1,j) \to f(i, j - 1)$。
• 如果 $s_i = \texttt{?}$，则 $f(i-1,j) \to f(i, j - 1), f(i-1,j) \to f(i, j + 1)$。

最终答案为 $f(n, 0)$

#include<bits/stdc++.h>
using namespace std;
const int N = 3e3 + 10, P = 998244353;
int n, f[N][N];
string s;
int main(){
    cin >> s;
    n = s.length(); 
    s = '#' + s;
    f[0][0] = 1;
    for(int i = 1; i <= n; i ++){
        if(s[i] == '('){
            for(int j = 0; j <= i - 1; j ++){
                f[i][j+1] = (1ll*f[i][j + 1] + f[i-1][j]) % P;
            }
        }else if(s[i] == ')'){
            for(int j = 1; j <= i - 1; j ++){
                f[i][j-1] = (1ll*f[i][j - 1] + f[i-1][j]) % P;
            }
        }else if(s[i] == '?'){
            for(int j = 0; j <= i - 1; j ++){
                f[i][j+1] = (1ll*f[i][j + 1] + f[i-1][j]) % P;
            }
            for(int j = 1; j <= i - 1; j ++){
                f[i][j-1] = (1ll*f[i][j - 1] + f[i-1][j]) % P;
            }
        }
    }
    cout << f[n][0];
    return 0;
}

SH2824 括号问号

题意：求 $\sum_{t 为 s 的子序列} f(t)$。

和上题类似，$f(i, j)$ 表示考虑到 $i$，前缀和为 $j$ 的方案数。

• 直接跳过 $s_i$，则 $f(i - 1, j) \to f(i, j)$。
• 将 $s _ i$ 加入子序列。
  • 如果 $s_i = \texttt{(}$，则 $f(i-1,j) \to f(i, j + 1)$。
  • 如果 $s_i = \texttt{)}$，则 $f(i-1,j) \to f(i, j - 1)$。
  • 如果 $s_i = \texttt{?}$，则 $f(i-1,j) \to f(i, j - 1), f(i-1,j) \to f(i, j + 1)$。

#include<bits/stdc++.h>
using namespace std;
const int N = 5e3 + 10, P = 998244353;
int n, f[N][N];
string s;
int main(){
    freopen("bracket.in", "r", stdin);
    freopen("bracket.out", "w", stdout);
    cin >> n >> s;
    s = '#' + s;
    f[0][0] = 1;
    for(int i = 1; i <= n; i ++){
        for(int j = 0; j <= i - 1; j ++){
            f[i][j] = (1ll*f[i][j] + f[i-1][j]) % P;
        }
        if(s[i] == '('){
            for(int j = 0; j <= i - 1; j ++){
                f[i][j+1] = (1ll*f[i][j + 1] + f[i-1][j]) % P;
            }
        }else if(s[i] == ')'){
            for(int j = 1; j <= i - 1; j ++){
                f[i][j-1] = (1ll*f[i][j - 1] + f[i-1][j]) % P;
            }
        }else if(s[i] == '?'){
            for(int j = 0; j <= i - 1; j ++){
                f[i][j+1] = (1ll*f[i][j + 1] + f[i-1][j]) % P;
            }
            for(int j = 1; j <= i - 1; j ++){
                f[i][j-1] = (1ll*f[i][j - 1] + f[i-1][j]) % P;
            }
        }
    }
    cout << f[n][0];
    return 0;
}