1. 括弧列の性質

(, ) からなる文字列 \(S\) が括弧列であることは以下の \(2\) つの条件を満たすことと同値です。

• 任意の \(i\) について、\(S\) の \(i\) 文字目までに含まれる ( の個数は ) の個数以上
• \(S\) に含まれる ( の個数と ) の個数は等しい

これは \(S\) の長さによる帰納法により示すことができます。

2. 数え上げ

\(dp_{i,j}\) を \(i\) 文字目までにある ? を ( あるいは ) に置き換える方法であって、任意の \(k \leq i\) に対し \(k\) 文字目までに含まれる ( の個数が ) の個数以上であり、（\(i\) 文字までの ( の個数）\(-\)（\(i\) 文字までの ) の個数）\( = j\) となるような方法の個数とします。求める答えは \(dp_{N,0}\) です。

以下、dp の遷移について解説します。 \(i - 1\) 文字目までにある ? が ( あるいは ) に置き換えられており、(\(i - 1\) 文字までの ( の個数）\(-\)（\(i - 1\) 文字までの ) の個数）\( = j\) のとき、(\(i\) 文字までの ( の個数）\(-\)（\(i\) 文字までの ) の個数）は \(S_i = \) ( のとき \(j+1\)、\(S_i = \) ) のとき \(j - 1\)、\(S_i = \) ? のとき \(S_i\) を ( に置き換えれば \(j+1\)、) に置き換えれば \(j-1\) となります。

したがって、\(dp_{i,j}\) の値を \(S_i =\) ( のとき \(dp_{i+1,j+1}\) に、\(S_i =\) ) のとき \(dp_{i+1,j-1}\) に、\(S_i =\) ? のとき \(dp_{i+1,j+1}\) と \(dp_{i+1,j-1}\) に足し合わせて遷移させていけばよいです。

dp の状態数が \(O(N^2)\)、遷移が \(O(1)\) なので時間計算量 \(O(N^2)\) でこの問題が解けました。

実装例

#include <iostream>
#include <string>
#include <vector>
#include <atcoder/modint>
using namespace std;
using mint = atcoder::static_modint<998244353>;

int main() {
	string s;
	cin >> s;
	int n = s.size();
	vector<vector<mint>> dp(n + 1, vector<mint>(n + 1));
	dp[0][0] = 1;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (s[i] != ')') dp[i + 1][j + 1] += dp[i][j];
			if (j != 0 && s[i] != '(') dp[i + 1][j - 1] += dp[i][j];
		}
	}
	cout << dp[n][0].val() << '\n';
}