题目描述

给定一个由(、) 和 ? 组成的非空字符串 S。用( 和 ) 替换 S 中的每个 ? 可以得到新的字符串方案有 $2^x$ 种，其中 $x$ 是 S 中 ? 的数量。求能得到括号字符串的方案数模 $998244353$ 的结果。

括号字符串定义如下：

• 如果字符串为空，则它是一个括号字符串。
• 如果字符串是 (、A、) 的连接形式，其中 A 是一个括号字符串，则它是一个括号字符串。
• 如果字符串是 A 和 B 的连接形式，其中 A 和 B 是非空的括号字符串，则它是一个括号字符串。

样例

input

(???(?

output

2

思路

首先要明确.对于一个可能合法的括号字符串，其任意前缀中(的数量一定要大于等于)的数量， 因为只有(出现在左侧才给右侧新出现的字符()/?)与它匹配的可能。

因此，状态定义如下：

f[i][j] 表示前i个字符中所有?被替换，对于所有$k <= i$, 前k个字符中(都比)多， 且前i个字符中未匹配(为 $j$ 个的方案数。

答案为f[N][0]， 即前N个字符中有0个(未匹配的方案。

转移方程：

• 如果第i个字符为(, 则前 $i - 1$ 个字符中的差值比前i个字符中的差值少1， 即f[i][j] = f[i - 1][j - 1]
• 如果第i个字符为)，则前 $i - 1$ 个字符中的差值比前i个字符中的差值多1， 即f[i][j] = f[i - 1][j + 1]
• 如果第i个字符为?, 则其中包括了以上两种情况

C++ 代码 $O(N^2)$

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int mod = 998244353;

const int N = 3010;

string s;

LL f[N][N];

int main()
{
    ios::sync_with_stdio(false);
    cin >> s;
    int n = s.length();
    f[0][0] = 1;
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 0; j <= n; ++j)
        {
             //f[i][j] 表示前i个字符中，将?全部替换后'(' 比 ')'多 j 个的方案数
            if(s[i - 1] == '(' && j >= 1)f[i][j] = f[i - 1][j - 1] % mod;
            else if(s[i - 1] == ')')f[i][j] = f[i - 1][j + 1] % mod;
            else if(s[i - 1] == '?')
            {
                if(j >= 1)f[i][j] = (f[i][j] + f[i - 1][j - 1] + f[i - 1][j + 1]) % mod;
                else f[i][j] = (f[i][j] + f[i - 1][j + 1]) % mod;
            }
        }
    }

    cout << f[n][0];
}