miope.cpp

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = 998244353;
const int MAXN = 3e3 + 10;
int dp[MAXN][MAXN];
int32_t main()
{
    cin.tie(0)->sync_with_stdio(0);
    string s; cin >> s;

    //Precisamos setar a base da dp, que é quando i = 0
    //O único caso no qual não há possibilidade é quando o primeiro caracter é ')'
    //,já que ele não vai fechar com ninguém.
    if(s[0] != ')') dp[0][1] = 1;

    //Aqui eu uso o operador ternário. Ele funciona da seguinte forma:
    //(condição, o que retorna se for verdadeira : o que retorna se for falsa)
    for(int i = 1; i < s.length(); i++)
    {
        for(int j = 0; j <= s.length(); j++)
        {
            //Caso '('
            if(s[i] == '(') dp[i][j] = (j > 0 ? dp[i - 1][j - 1] : 0);
            //Caso ')'
            else if(s[i] == ')') dp[i][j] = dp[i - 1][j + 1];
            //Caso '?'
            else
            {
                dp[i][j] = dp[i - 1][j + 1] + (j ? dp[i - 1][j - 1] : 0);
                dp[i][j] %= MOD;
            }
        }
    }

    cout << dp[s.length() - 1][0];
}