結果
問題 | No.2106 Wild Cacco |
ユーザー |
👑 |
提出日時 | 2022-10-28 14:48:58 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 924 ms / 2,000 ms |
コード長 | 912 bytes |
コンパイル時間 | 151 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 119,312 KB |
最終ジャッジ日時 | 2024-07-05 19:22:58 |
合計ジャッジ時間 | 17,013 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 30 |
ソースコード
MOD = 998244353 S = input() n = len(S) dp = [[0] * 2 for _ in range(n)] dp[0][0] = 1 for s in S: ndp = [[0] * 2 for _ in range(n)] def f1(): for i in range(n - 1): ndp[i + 1][0] += dp[i][0] ndp[i + 1][1] += dp[i][1] ndp[i + 1][0] %= MOD ndp[i + 1][1] %= MOD def f2(): for i in range(n - 1): ndp[i][0] += dp[i + 1][0] ndp[i][1] += dp[i + 1][1] ndp[i][0] %= MOD ndp[i][1] %= MOD def f3(): for i in range(n - 1): ndp[i + 1][0] += dp[i][0] ndp[i + 1][0] %= MOD ndp[i][1] += dp[i + 1][1] + dp[i + 1][0] ndp[i][1] %= MOD if s == "(": f1() elif s == ")": f2() elif s == "?": f3() else: f1() f2() f3() dp = ndp ans = dp[0][0] + dp[0][1] print(ans % MOD)