結果
問題 | No.2106 Wild Cacco |
ユーザー |
👑 |
提出日時 | 2022-09-29 21:59:43 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,708 bytes |
コンパイル時間 | 5,012 ms |
コンパイル使用メモリ | 102,252 KB |
実行使用メモリ | 68,480 KB |
最終ジャッジ日時 | 2024-12-30 11:37:00 |
合計ジャッジ時間 | 64,195 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 9 TLE * 21 |
ソースコード
#include <stdio.h>const int Mod = 998244353;int naive(char s[]){int l;for (l = 0; s[l] != 0; l++);if (l % 2 != 0) return 0;unsigned int dp[2003][4003] = {}, tmp;int i, j, k, ll = l / 2;for (k = 0, dp[0][0] = 1; k < l; k++) {if (s[k] == '(') {for (i = 0; i <= k / 2; i++) {for (j = i * 2 + k % 2; j <= k; j += 2) {if (dp[i][j] == 0) continue;tmp = dp[i][j];dp[i][j] = 0;while (tmp >= Mod) tmp -= Mod;dp[i][j+1] += tmp;}}} else if (s[k] == ')') {for (i = 0; i <= k / 2; i++) {for (j = i * 2 + k % 2; j <= k; j += 2) {if (dp[i][j] == 0) continue;tmp = dp[i][j];dp[i][j] = 0;while (tmp >= Mod) tmp -= Mod;if (j > i * 2) dp[i][j-1] += tmp;else if (i > 0) dp[i-1][j-1] += tmp;}}} else if (s[k] == '?') {for (i = 0; i <= k / 2; i++) {for (j = i * 2 + k % 2; j <= k; j += 2) {if (dp[i][j] == 0) continue;tmp = dp[i][j];dp[i][j] = 0;while (tmp >= Mod) tmp -= Mod;if (j > i * 2) dp[i+1][j+1] += tmp;else dp[i][j+1] += tmp;}}} else {for (i = 0; i <= k / 2; i++) {for (j = i * 2 + k % 2; j <= k; j += 2) {if (dp[i][j] == 0) continue;tmp = dp[i][j];dp[i][j] = 0;while (tmp >= Mod) tmp -= Mod;dp[i][j+1] += tmp;if (j > i * 2) dp[i][j-1] += tmp;else if (i > 0) dp[i-1][j-1] += tmp;if (j > i * 2) dp[i+1][j+1] += tmp;else dp[i][j+1] += tmp;}}}}long long ans = 0;for (i = 0; i <= ll; i++) ans += dp[i][i*2];return ans % Mod;}int main(){char s[4001];scanf("%s", s);printf("%d\n", naive(s));fflush(stdout);return 0;}