結果
問題 |
No.3043 括弧列の数え上げ
|
ユーザー |
![]() |
提出日時 | 2025-01-24 02:45:45 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 87 ms / 2,000 ms |
コード長 | 570 bytes |
コンパイル時間 | 434 ms |
コンパイル使用メモリ | 82,440 KB |
実行使用メモリ | 76,288 KB |
最終ジャッジ日時 | 2025-01-24 02:45:51 |
合計ジャッジ時間 | 4,488 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 45 |
ソースコード
mod = 998244353 N = int(input()) if N % 2 == 1: print(0) exit() N //= 2 ans = [0] * (N + 1) catalan = [1, 1] for i in range(2, N + 1): catalan.append(catalan[-1] * 2 * (2 * i - 1) * pow(i + 1, -1, mod) % mod) for i in range(2, N + 1): ans[i] = (ans[i - 1] + catalan[i - 1] * (i - 1)) % mod # ( xxx ) for j in range(1, i): # xxx (...) ans[i] += ans[j] * catalan[i - j - 1] % mod ans[i] += catalan[j] * ans[i - j - 1] % mod ans[i] += catalan[j] * catalan[i - j - 1] * (i - j - 1) % mod ans[i] %= mod print(ans[N])