abc312D

IGA_Indigo · 2025-03-30 11:36:51 · 个人记录

#include<bits/stdc++.h>
using namespace std;
long long read(){
    long long x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-'){
            f=-1;
        }
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
void write(long long x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9){
        write(x/10);
    }
    putchar(x%10+'0');
    return ;
}
int f[3005][6005];
int main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    string s;//)-1, (+1
    cin>>s;
    int n=s.size();
    s=' '+s;
    f[0][3003]=1;
    for(int i=1;i<=n;i++){
        if(s[i]==')'){
            for(int j=3003;j<=6000;j++){
                if(f[i-1][j]){
                    f[i][j-1]+=f[i-1][j];
                    f[i][j-1]%=998244353;
                }
            }
        }
        if(s[i]=='('){
            for(int j=3003;j<=6000;j++){
                if(f[i-1][j]){
                    f[i][j+1]+=f[i-1][j];
                    f[i][j+1]%=998244353;
                }
            }
        }
        if(s[i]=='?'){
            for(int j=3003;j<=6000;j++){
                if(f[i-1][j]){
                    f[i][j+1]+=f[i-1][j];
                    f[i][j+1]%=998244353;
                    f[i][j-1]+=f[i-1][j];
                    f[i][j-1]%=998244353;
                }
            }
        }
    }
    write(f[n][3003]%998244353);
    return 0;
}