解説
この問題は動的計画法 (DP) を用いて解くことが出来ます。
部分列の条件に従い、以下のように状態遷移を考えることが出来ます。
状態を以下のように定義します:
dp[i][j]: i番目までの文字で、部分列が状態jとなるものの個数
部分列の状態jを以下のように定義します:
- 0: まだ何もできていない
- 1:
(までできた - 2:
(^までできた - 3:
(^^までできた - 4:
(^^)完成
次に、状態遷移を考えます:
- 文字が
(の場合、状態0から状態1へ遷移する - 文字が
^の場合、状態1から状態2へ、そして状態2から状態3へ遷移する - 文字が
)の場合、状態3から状態4へ遷移する
状態jの数を更新する際、前の状態の数を継承することも忘れてはいけません。これにより、状態0から状態3までの数は次の文字に対しても適用されます。
実装
xxxxxxxxxx1
2
3
using namespace std;4
using namespace atcoder;5
using mint = modint998244353;6
7
int main() {8
int n;9
cin >> n;10
string s;11
cin >> s;12
13
vector<vector<mint>> dp(n+1, vector<mint>(5));14
dp[0][0] = 1;15
for(int i = 0;i < n; ++i){16
if(s[i] == '('){17
dp[i+1][1] += dp[i][0];18
}else if(s[i] == '^'){19
dp[i+1][2] += dp[i][1];20
dp[i+1][3] += dp[i][2];21
}else{ // )22
dp[i+1][4] += dp[i][3];23
}24
25
//状態の継承26
for(int j = 0;j < 5; ++j){27
dp[i+1][j] += dp[i][j];28
}29
}30
31
cout << dp[n][4].val() << endl;32
return 0;33
}