結果
問題 | No.3099 Parentheses Decomposition |
ユーザー |
![]() |
提出日時 | 2025-01-13 00:49:50 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 23 ms / 2,000 ms |
コード長 | 689 bytes |
コンパイル時間 | 2,228 ms |
コンパイル使用メモリ | 196,988 KB |
実行使用メモリ | 7,600 KB |
最終ジャッジ日時 | 2025-01-13 00:49:56 |
合計ジャッジ時間 | 3,345 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 20 |
ソースコード
#include<bits/stdc++.h> using namespace std; #include<atcoder/modint> typedef atcoder::modint998244353 mint; int main() { int n; cin >> n; string s; cin >> s; int type = 0; if (s[1] == ')') type = 1; if (type == 0) { vector<mint> fact(n+1), factinv(n+1); fact[0] = 1; for (int i=1; i<=n; i++) fact[i] = fact[i-1] * i; factinv[n] = fact[n].inv(); for (int i=n-1; i>=0; i--) factinv[i] = factinv[i+1] * (i+1); auto cmb = [&](int n, int k) -> mint { return fact[n] * factinv[k] * factinv[n-k]; }; mint ans = 0; for (int i=0; i<=n/2; i++) { ans += cmb(n/2,i) * cmb(n/2,i); } cout << ans.val() << endl; }else{ cout << mint(2).pow(n/2).val() << endl; } }