結果
問題 | No.2106 Wild Cacco |
ユーザー |
|
提出日時 | 2022-10-21 22:01:09 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 717 ms / 2,000 ms |
コード長 | 1,588 bytes |
コンパイル時間 | 217 ms |
コンパイル使用メモリ | 82,060 KB |
実行使用メモリ | 141,412 KB |
最終ジャッジ日時 | 2024-07-01 06:35:33 |
合計ジャッジ時間 | 16,679 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 30 |
ソースコード
import sys,random,bisect from collections import deque,defaultdict from heapq import heapify,heappop,heappush from itertools import combinations, permutations from math import log,gcd input = lambda :sys.stdin.readline() mi = lambda :map(int,input().split()) li = lambda :list(mi()) mod = 998244353 s = input().rstrip() n = len(s) dp_left = [[0] * (n//2+1) for i in range(n+1)] dp_left[0][0] = 1 for i in range(n): for j in range(n//2+1): if (s[i] == "(" or s[i] == ".") and j+1 <= n//2: dp_left[i+1][j+1] += dp_left[i][j] dp_left[i+1][j+1] %= mod if (s[i] == ")" or s[i] == ".") and 0 <= j-1: dp_left[i+1][j-1] += dp_left[i][j] dp_left[i+1][j-1] %= mod if (s[i] == "?" or s[i] == ".") and j+1 <= n//2: dp_left[i+1][j+1] += dp_left[i][j] dp_left[i+1][j+1] %= mod res = dp_left[n][0] #print(res,dp_left) dp_right = [0] * (n//2+1) dp_right[0] = 1 for i in range(n)[::-1]: ndp = [0] * (n//2+1) for j in range(n//2+1): if (s[i] == ")" or s[i] == ".") and j+1 <= n//2: ndp[j+1] += dp_right[j] ndp[j+1] %= mod if (s[i] == "(" or s[i] == ".") and 0 <= j-1: ndp[j-1] += dp_right[j] ndp[j-1] %= mod if (s[i] == "?" or s[i] == ".") and j+1 <= n//2: ndp[j+1] += dp_right[j] ndp[j+1] %= mod tmp = dp_left[i][j+1] * dp_right[j] % mod res = (res + tmp) % mod dp_right = ndp print(res)