abc312d <dp, 括号匹配方案数>

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
using LL = long long;
using PII = pair<int, int>;
const int N = 3010, mod = 998244353;
LL dp[N][N];

void solv()
{
    string s; cin >> s; s = "$" + s;
    int n = s.size() - 1;
    dp[0][0] = 1;
    for (int i = 1; i <= n; i ++)
    {
        for (int j = 1; j <= i; j ++)
        {
            if (s[i] == '(')      dp[i][j] += dp[i-1][j - 1];
            else if (s[i] == ')') dp[i][j-1] += dp[i-1][j];
            else
            {
                dp[i][j] += dp[i-1][j - 1];
                dp[i][j-1] += dp[i-1][j];                
            }
            dp[i][j] %= mod;
            dp[i][j-1] %= mod;
        }
    }
    cout << dp[n][0] << endl;
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T = 1;
	// cin >> T;
    while (T --)
    {
        solv();
    }
    return 0;
}