結果
問題 |
No.3099 Parentheses Decomposition
|
ユーザー |
|
提出日時 | 2025-04-11 21:26:04 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 561 ms / 2,000 ms |
コード長 | 992 bytes |
コンパイル時間 | 191 ms |
コンパイル使用メモリ | 82,300 KB |
実行使用メモリ | 103,572 KB |
最終ジャッジ日時 | 2025-04-11 21:26:12 |
合計ジャッジ時間 | 7,491 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 20 |
ソースコード
n = int(input()) s = list(input().rstrip()) mod = 998244353 if s[0] == '(' and s[1] == ')': ans = pow(2,n//2,mod) print(ans) else: class comb(): def __init__(self,n,mod): self.fact = [0] * (n+1) self.fact_inv = [0] * (n+1) self.mod = mod self.fact[1] = 1 self.fact_inv[1] = pow(1,mod-2,mod) self.fact[0] = 1 self.fact_inv[0] = 1 for i in range(2,n+1): self.fact[i] = (self.fact[i-1] * i) % mod self.fact_inv[i] = (self.fact_inv[i-1] * pow(i,mod-2,mod)) % mod def ncr(self,n,r): if n-r < 0: return 0 return (self.fact[n] * self.fact_inv[r] * self.fact_inv[n-r]) % self.mod def nhr(self,n,r): return self.ncr(n+r-1,r) c = comb(500000+10,mod) ans = 0 for i in range(n//2 + 1): x = c.ncr(n//2,i) ans += x * x ans %= mod print(ans)