結果
問題 | No.3099 Parentheses Decomposition |
ユーザー |
|
提出日時 | 2025-04-11 21:50:10 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 32 ms / 2,000 ms |
コード長 | 1,346 bytes |
コンパイル時間 | 8,154 ms |
コンパイル使用メモリ | 351,560 KB |
実行使用メモリ | 19,540 KB |
最終ジャッジ日時 | 2025-04-11 21:50:20 |
合計ジャッジ時間 | 8,440 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 20 |
ソースコード
#pragma GCC optimize("O3") #include <bits/stdc++.h> #include <atcoder/all> using namespace std; typedef long long ll; const int INF = 1<<30; const ll INFLL = 1LL<<60; const ll MOD = 998244353; const double INFD = 1.0E10; const int dx[4] = {1, 0, -1, 0}; const int dy[4] = {0, -1, 0, 1}; //const int dx[8] = {1, 1, 0, -1, -1, -1, 0, 1}; //const int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1}; using Pair = pair<ll, ll>; using Graph = vector<vector<ll, ll> >; using mint = atcoder::modint998244353; struct combination{ vector<mint> fact, ifact; combination(int n):fact(n+1), ifact(n+1){ assert(n < MOD); fact[0] = 1; for (int i=1; i <= n; i++) fact[i] = fact[i-1] * i; ifact[n] = fact[n].inv(); for (int i=n; i >= 1; i--) ifact[i-1] = ifact[i] * i; } mint operator()(int n, int k){ if (k < 0 || n < k) return 0; return fact[n] * ifact[k] * ifact[n-k]; } } comb(2000005); int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); cout << fixed << setprecision(15); int n; string s; cin >> n >> s; if (s[0] != s[1]) cout << mint(2).pow(n / 2).val() << endl; else{ mint ans = 0; for (int i = 0; i <= n / 2; i++){ ans += comb(n / 2, i) * comb(n / 2, i); } cout << ans.val() << endl; } return 0; }