1. Properties of parenthesis string

A string \(S\) consisting of ( and ) is a parenthesis string if and only if the following two conditions are satisfied.

• For all \(i\), the first \(i\) characters of \(S\) contains more occurrences of ( than of )
• \(S\) contains the same number of ( and ).

This can be shown by induction on the length of \(S\).

2. Counting

Let \(dp_{i,j}\) be the number of ways to replace each occurrence of ? with ( or ) in the first \(i\) characters, such that ( occurs more than ) in the first \(k\) characters for all \(k \leq i\), and (the number of (s in the first \(i\) characters) \(-\) (the number of )s in the first \(i\) characters) \( = j\). What we want is \(dp_{N,0}\).

We describe the transitions of the DP (Dynamic Programming). If each ? in the first \((i-1)\) characters is replaced with ( and ), and (the number of (s in the first \((i-1)\) characters) \(-\) (the number of )s in the first \((i-1)\) characters) \(= j\), then (the number of (s in the first \(i\) characters) \(-\) (the number of )s in the first \(i\) characters) becomes \(j+1\) if \(S_i = \) (, \(j-1\) if \(S_i = \) ), and \(j+1\) and \(j-1\) if \(S_i = \) ? is replaced with ( and ), respectively.

Therefore, the transition is as follows: if \(S_i =\) (, then add \(dp_{i,j}\) to \(dp_{i+1,j+1}\); if \(S_i =\) ), then add it to \(dp_{i+1,j-1}\); if \(S_i =\) ?, then add it to \(dp_{i+1,j+1}\) and \(dp_{i+1,j+1}\).

Since there are \(O(N^2)\) states in the DP, and each transition costs \(O(1)\), so the problem has been solved in a total of \(O(N^2)\) time.

Sample code

#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';
}