ABC312D-solution

igAC · 2023-07-30 16:05:29 · 题解

\text{Description}

闲话：写了这么多篇题解，现在才想起来题目描述应该是用 Description 而不是 Describe。

洛谷 link

ATlink

简要题意：

给定一个由 ( ) ? 组成的字符串。

你可以用 ( 或 ) 替换 ?。

问使这个字符串成为一个合法括号序列的替换方案数。

\text{Solution}

简单题。

设 f_{i,j} 表示当前在第 i 位，且 ( 比 ) 多 j 个的方案数。

分情况讨论：

若 s_i=(，f_{i,j} 可从 f_{i-1,j-1} 转移而来，即 f[i][j]+=f[i-1][j-1]；

若 s_i=)，f_{i,j} 可从 f_{i-1,j+1} 转移而来，即 f[i][j]+=f[i-1][j+1]；

若 s_i=?，包含以上两种情况 f[i][j]+=f[i-1][j-1]+f[i-1][j+1]。

具体实现可参考代码。

\text{Code}

#include<bits/stdc++.h>
#define int long long
#define N 3005
#define Mod 998244353
using namespace std;
int read(){
    int x=0,f=1,ch=getchar();
    for(;!isdigit(ch);ch=getchar()) f=(ch=='-')?-1:1;
    for(;isdigit(ch);ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
    return x*f;
}
int n,f[N][N];
char a[N];
signed main(){
    scanf("%s",a+1),n=strlen(a+1),f[0][0]=1;
    for(int i=1;i<=n;++i){
        for(int j=0;j<=n;++j){
            if(a[i]!='?'){
                int w=(a[i]=='('?1:-1);
                if(j>=w) f[i][j]=(f[i][j]+f[i-1][j-w])%Mod;
            }
            else{
                f[i][j]=(f[i][j]+f[i-1][j+1])%Mod;
                if(j) f[i][j]=(f[i][j]+f[i-1][j-1])%Mod;
            }
        }
    }
    printf("%lld",f[n][0]%Mod);
    return 0;
}