結果
問題 | No.3099 Parentheses Decomposition |
ユーザー |
![]() |
提出日時 | 2025-04-11 21:26:18 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 25 ms / 2,000 ms |
コード長 | 7,969 bytes |
コンパイル時間 | 5,837 ms |
コンパイル使用メモリ | 334,004 KB |
実行使用メモリ | 10,164 KB |
最終ジャッジ日時 | 2025-04-11 21:26:27 |
合計ジャッジ時間 | 6,754 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 20 |
ソースコード
#include <bits/stdc++.h> #if __has_include(<atcoder/all>) #include <atcoder/all> std::istream &operator>>(std::istream &is, atcoder::modint &v) { long long value; is >> value; v = value; return is; } std::ostream &operator<<(std::ostream &os, const atcoder::modint &v) { os << v.val(); return os; } std::ostream &operator<<(std::ostream &os, const atcoder::modint998244353 &v) { os << v.val(); return os; } std::istream &operator>>(std::istream &is, atcoder::modint998244353 &v) { long long x; is >> x; v = x; return is; } std::ostream &operator<<(std::ostream &os, const atcoder::modint1000000007 &v) { os << v.val(); return os; } std::istream &operator>>(std::istream &is, atcoder::modint1000000007 &v) { long long x; is >> x; v = x; return is; } #endif using namespace std; using ll = long long; using lint = __int128_t; using pll = pair<ll, ll>; #define newl '\n'; #define rep(i, s, t) for (ll i = s; i < (ll)(t); i++) #define rrep(i, s, t) for (ll i = (ll)(t) - 1; i >= (ll)(s); i--) #define all(x) begin(x), end(x) #define SZ(x) ll(x.size()) #define eb emplace_back #define pb push_back #define TT template <typename T> TT using vec = vector<T>; TT using vvec = vec<vec<T>>; TT using vvvec = vec<vvec<T>>; TT using minheap = priority_queue<T, vector<T>, greater<T>>; TT using maxheap = priority_queue<T>; TT bool chmin(T &x, T y) { return x > y ? (x = y, true) : false; } TT bool chmax(T &x, T y) { return x < y ? (x = y, true) : false; } TT T smod(T x, T mod) { x %= mod; if (x < 0) x += mod; return x; } TT bool rng(T l, T x, T r) { return l <= x && x < r; } TT T flr(T a, T b) { if (b < 0) a = -a, b = -b; return a >= 0 ? a / b : (a + 1) / b - 1; } TT T cil(T a, T b) { if (b < 0) a = -a, b = -b; return a > 0 ? (a - 1) / b + 1 : a / b; } TT T sqr(T x) { return x * x; } //{0, 1, ... } -> {p[0], p[1], ...} template <typename T, typename S> void rearrange(vector<T> &A, vector<S> const &p) { assert(p.size() == A.size()); vector<T> a = A; for (int i = 0; i < ssize(A); ++i) { a[i] = A[p[i]]; } swap(a, A); } template <typename T, typename S, typename... Ts> void rearrange(vector<T> &A, vector<S> p, vector<Ts> &...rest) { rearrange(A, p); (rearrange(rest, p), ...); } template <typename T, typename Compare, typename... Ts> void rearrange(vector<T> &A, Compare cmp, vector<Ts> &...rest) { vector<int> p(ssize(A)); iota(p.begin(), p.end(), 0); sort(p.begin(), p.end(), cmp); rearrange(A, p); (rearrange(rest, p), ...); } struct io_setup { io_setup() { ios::sync_with_stdio(false); std::cin.tie(nullptr); cout << fixed << setprecision(15); } } io_setup; template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &p) { os << p.first << " " << p.second; return os; } TT ostream &operator<<(ostream &os, const vector<T> &v) { for (size_t i = 0; i < v.size(); i++) { os << v[i] << (i + 1 != v.size() ? " " : ""); } return os; } template <typename T, size_t n> ostream &operator<<(ostream &os, const array<T, n> &v) { for (size_t i = 0; i < n; i++) { os << v[i] << (i + 1 != n ? " " : ""); } return os; } template <typename T> ostream &operator<<(ostream &os, const vvec<T> &v) { for (size_t i = 0; i < v.size(); i++) { os << v[i] << (i + 1 != v.size() ? "\n" : ""); } return os; } TT istream &operator>>(istream &is, vector<T> &v) { for (size_t i = 0; i < v.size(); i++) { is >> v[i]; } return is; } #if __has_include(<debug/debug.hpp>) #include <debug/debug.hpp> #else #define dbg(...) true #define DBG(...) true #define OUT(...) true #endif template <typename T, long long mod> struct combination { vector<long long> fac, ifac, inv; long long N; combination() { fac.resize(2, 1); ifac.resize(2, 1); inv.resize(2, 1); N = 1; } void reserve(long long n) { expand(n); } T operator()(int n, int k) { return C(n, k); } T raw(long long n, long long k) const { if (k < 0) return 0; if (k == 0) return 1; if (n < k) return 0; if (n - k < k) { k = n - k; } long long p = 1, q = 1; for (long long i = 0; i < k; i++) { p *= (n - i) % mod; p %= mod; q *= (k - i) % mod; q %= mod; } return p * modinv(q) % mod; } T C(int n, int k) { if (k < 0) return 0; if (k == 0) return 1; if (n < k) return 0; if (N < n) expand(n); return fac[n] * ifac[n - k] % mod * ifac[k] % mod; } T P(int n, int k) { if (k < 0) return 0; if (k == 0) return 1; if (n < k) return 0; if (N < n) expand(n); return fac[n] * ifac[n - k] % mod; } T B(int n) { if (N < n) expand(n); return (n < 0 ? 0 : fac[n]); } T invB(int n) { if (N < n) expand(n); return (n < 0 ? 0 : ifac[n]); } T H(int n, int k) { return C(n + k - 1, k); } T Cn(int n) { return C(2 * n, n) * inv[n + 1] % mod; } private: constexpr static bool is_prime_constexpr(long long x) { if (x <= 1) return false; for (long long i = 2; i * i <= x; i++) { if (x % i == 0) return false; } return true; } static_assert(is_prime_constexpr(mod), "mod must be prime"); static_assert(__int128_t(mod - 1) * (mod - 1) <= __int128_t(LLONG_MAX), "(mod - 1) * (mod - 1) <= LLONG_MAX must be satisfied"); long long extgcd(long long a, long long b, long long &x, long long &y) const { if (b == 0) { x = 1; y = 0; return a; } auto d = extgcd(b, a % b, y, x); y -= a / b * x; return d; } long long modinv(long long a) const { long long x, y; extgcd(a, mod, x, y); x %= mod; if (x < 0) x += mod; return x; } void expand(long long new_max_n) { if (new_max_n <= N) return; long long nx = N; // 2冪で大きくしていく。 while (nx < new_max_n) nx <<= 1; new_max_n = nx; long long pre = N; N = new_max_n; fac.resize(N + 1); ifac.resize(N + 1); inv.resize(N + 1); for (long long i = pre + 1; i <= N; i++) { fac[i] = fac[i - 1] * i % mod; } ifac[N] = modinv(fac[N]); inv[N] = ifac[N] * fac[N - 1] % mod; for (long long i = N - 1; i >= pre + 1; i--) { ifac[i] = ifac[i + 1] * (i + 1) % mod; inv[i] = ifac[i] * fac[i - 1] % mod; } return; } }; /* @brief combination @docs doc/cmb.md */ using combination998244353 = combination<atcoder::modint998244353, 998244353>; combination998244353 cmb; using mint = atcoder::modint998244353; int main() { auto type = [&](string A) { ll n = A.size(); rep(i, 0, n / 2) if (A[i] != '(') return 1; return 0; }; ll n; cin >> n; string S; cin >> S; if (type(S) == 0) { mint ret = 0; rep(c, 0, n/2 + 1) { ret += cmb(n/2, c) * cmb(n/2, c); } cout << ret << endl; } else { mint ret = 0; rep(c, 0, n/2 + 1) { ret += cmb(n/2, c); } cout << ret << endl; } } /* 同じ議論を繰り返さない do smth instead of nothing and stay organized WRITE STUFF DOWN DON'T GET STUCK ON ONE APPROACH */