#1081874 (C++23) No.3138 Minimum Bracket Subsequence

提出ソース
結果

問題	No.3138 Minimum Bracket Subsequence
ユーザー	PNJ
提出日時	2025-05-02 22:54:21
言語	C++23 (gcc 13.3.0 + boost 1.87.0)
結果	TLE
実行時間	-
コード長	15,992 bytes
コンパイル時間	4,628 ms
コンパイル使用メモリ	298,756 KB
実行使用メモリ	47,824 KB
最終ジャッジ日時	2025-05-02 22:54:30
合計ジャッジ時間	8,303 ms
ジャッジサーバーID （参考情報）	judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 2
other	AC * 16 TLE * 1 -- * 19
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include <bits/stdc++.h>
using namespace std;

template <int mod>
struct modint {
  static constexpr uint32_t umod = uint32_t(mod);
  static_assert(umod < (uint32_t(1) << 31));
  uint32_t val;

  static modint raw(uint32_t v) {
    modint x;
    x.val = v % umod;
    return x;
  }

  constexpr modint() : val(0) {}
  constexpr modint(uint32_t x) : val(x % umod) {}
  constexpr modint(uint64_t x) : val(x % umod) {}
  constexpr modint(__uint128_t x) : val(x % umod) {}
  constexpr modint(int x) : val((x %= int(umod)) < 0 ? x + umod : x) {};
  constexpr modint(long long x) : val((x %= int(umod)) < 0 ? x + umod : x) {};
  constexpr modint(__int128_t x) : val((x %= int(umod)) < 0 ? x + umod : x) {};

  bool operator<(const modint &other) const { return val < other.val; }
  modint &operator+=(const modint &p) {
    if ((val += p.val) >= umod) val -= umod;
    return *this;
  }
  modint &operator-=(const modint &p) {
    if ((val += umod - p.val) >= umod) val -= umod;
    return *this;
  }
  modint &operator*=(const modint &p) {
    val = uint64_t(val) * p.val % umod;
    return *this;
  }
  modint &operator/=(const modint &p) {
    val = uint64_t(val) * p.inverse().val % umod;
    return *this;
  }
  modint operator-() const { return modint::raw(val ? umod - val : uint32_t(0)); }
  modint operator+(const modint &p) const { return modint(*this) += p; }
  modint operator-(const modint &p) const { return modint(*this) -= p; }
  modint operator*(const modint &p) const { return modint(*this) *= p; }
  modint operator/(const modint &p) const { return modint(*this) /= p; }
  bool operator==(const modint &p) const { return val == p.val; }
  bool operator!=(const modint &p) const { return val != p.val; }

  modint inverse() const {
    int a = val, b = umod, s = 1, t = 0;
    while (1) {
      if (a == 1) return modint(s);
      t -= (b / a) * s;
      b %= a;
      if (b == 1) return modint(t + umod);
      s -= (a / b) * t;
      a %= b;
    }
  }

  modint pow(long long n) const {
    n %= (long long)(umod);
    if (n < 0) n += umod - 1;
    modint res(1), a(val);
    while (n > 0) {
      if (n & 1) res *= a;
      a *= a;
      n >>= 1;
    }
    return res;
  }

  uint32_t get() const { return val; }

  static constexpr int get_mod() { return mod; }
  
  static constexpr pair<int, int> ntt_info() {
    if (mod == 167772161) return {25, 17};
    if (mod == 469762049) return {26, 30};
    if (mod == 754974721) return {24, 362};
    if (mod == 880803841) return {23, 211};
    if (mod == 998244353) return {23, 31};
    return {-1, -1};
  }
};

template <int mod>
void rd(modint<mod> &x) {
  uint32_t y;
  cin >> y;
  x = y;
}

template <int mod>
void wt(modint<mod> x) {
  wt(x.val);
}

template <typename mint>
mint fact(long long n) {
  static vector<mint> res = {1, 1};
  static long long le = 1;
  if (n < 0) return mint(0);
  while (le <= n){
    le++;
    res.push_back(res[le - 1] * le);
  }
  return res[n];
}

template <typename mint>
mint fact_inv(long long n) {
  static vector<mint> res = {1, 1};
  static long long le = 1;
  if (n < 0) return mint(0);
  while (le <= n) {
    le++;
    res.push_back(res[le - 1] / le);
  }
  return res[n];
}

template <typename mint>
mint binom(long long n, long long r) {
  if (n < 0 || r < 0 || n < r) return 0;
  mint res = fact<mint>(n) * (fact_inv<mint>(n - r) * fact_inv<mint>(r));
  return res;
}

template <class mint>
void ntt(vector<mint> &a, bool inverse) {
  const int mod = mint::get_mod();
  const int rank2 = mint::ntt_info().first;
  static array<mint, 30> root, rate2, rate3, iroot, irate2, irate3;

  static bool prepared = 0;
  if (!prepared) {
    prepared = 1;
    root[rank2] = mint::ntt_info().second;
    iroot[rank2] = mint(1) / root[rank2];
    for (int i = rank2 - 1; i >= 0; i--) {
      root[i] = root[i + 1] * root[i + 1];
      iroot[i] = iroot[i + 1] * iroot[i + 1];
    }

    mint prod = 1, iprod = 1;
    for (int i = 0; i < rank2; i++) {
      rate2[i] = root[i + 2] * prod;
      irate2[i] = iroot[i + 2] * iprod;
      prod *= iroot[i + 2];
      iprod *= root[i + 2];
    }

    prod = 1, iprod = 1;
    for (int i = 0; i < rank2 - 1; i++) {
      rate3[i] = root[i + 3] * prod;
      irate3[i] = iroot[i + 3] * iprod;
      prod *= iroot[i + 3];
      iprod *= root[i + 3];
    }
  }

  int n = int(a.size()), h = (n == 0 ? -1 : 31 - __builtin_clz(n));

  if (!inverse) {
    int le = 0;
    while (le < h) {
      if (h - le == 1) {
        int p = 1 << (h - le - 1);
        mint rot = 1;
        for (int s = 0; s < (1 << le); s++) {
          int offset = s << (h - le);
          for (int i = 0; i < p; i++) {
            auto l = a[i + offset];
            auto r = a[i + offset + p] * rot;
            a[i + offset] = l + r;
            a[i + offset + p] = l - r;
          }
          rot *= rate2[((~s & -~s) == 0 ? -1 : 31 - __builtin_clz(~s & -~s))];
        }
        le++;
      }
      else {
        int p = 1 << (h - le - 2);
        mint rot = 1, imag = root[2];
        for (int s = 0; s < (1 << le); s++) {
          mint rot2 = rot * rot;
          mint rot3 = rot2 * rot;
          int offset = s << (h - le);
          for (int i = 0; i < p; i++) {
            uint64_t mod2 = uint64_t(mod) * mod;
            uint64_t a0 = a[i + offset].get();
            uint64_t a1 = uint64_t(a[i + offset + p].get()) * rot.get();
            uint64_t a2 = uint64_t(a[i + offset + p * 2].get()) * rot2.get();
            uint64_t a3 = uint64_t(a[i + offset + p * 3].get()) * rot3.get();
            uint64_t a1na3imag = (a1 + mod2 - a3) % mod * imag.get();
            a[i + offset] = a0 + a2 + a1 + a3;
            a[i + offset + p] = a0 + a2 + (2 * mod2 - (a1 + a3));
            a[i + offset + p * 2] = a0 + mod2 - a2 + a1na3imag;
            a[i + offset + p * 3] = a0 + mod2 - a2 + (mod2 - a1na3imag);
          }
          rot = rot * rate3[((~s & -~s) == 0 ? -1 : 31 - __builtin_clz(~s & -~s))];
        }
        le = le + 2;
      }
    }
  }
  else {
    mint coef = mint(n).inverse();
    for (int i = 0; i < n; i++) {
      a[i] *= coef;
    }
    int le = h;
    while (le) {
      if (le == 1) {
        int p = 1 << (h - le);
        mint irot = 1;
        for (int s = 0; s < (1 << (le - 1)); s++) {
          int offset = s << (h - le + 1);
          for (int i = 0; i < p; i++) {
            uint64_t l = a[i + offset].get();
            uint64_t r = a[i + offset + p].get();
            a[i + offset] = l + r;
            a[i + offset + p] = (mod + l - r) * irot.get();
          }
          irot *= irate2[((~s & -~s) == 0 ? -1 : 31 - __builtin_clz(~s & -~s))];
          }
        le--;
      }
      else {
        int p = 1 << (h - le);
        mint irot = 1, iimag = iroot[2];
        for (int s = 0; s < (1 << (le - 2)); s++) {
          mint irot2 = irot * irot;
          mint irot3 = irot2 * irot;
          int offset = s << (h - le + 2);
          for (int i = 0; i < p; i++) {
            uint64_t a0 = a[i + offset].get();
            uint64_t a1 = a[i + offset + p].get();
            uint64_t a2 = a[i + offset + p * 2].get();
            uint64_t a3 = a[i + offset + p * 3].get();
            uint64_t a2na3iimag = (mod + a2 - a3) * iimag.get() % mod;
            a[i + offset] = a0 + a1 + a2 + a3;
            a[i + offset + p] = (a0 + mod - a1 + a2na3iimag) * irot.get();
            a[i + offset + p * 2] = (a0 + a1 + 2 * mod - a2 - a3) * irot2.get();
            a[i + offset + p * 3] = (a0 + 2 * mod - a1 - a2na3iimag) * irot3.get();
          }
          irot *= irate3[((~s & -~s) == 0 ? -1 : 31 - __builtin_clz(~s & -~s))];
        }
        le = le - 2;
      }
    }
  }
}

template <class mint>
vector<mint> convolution_naive(vector<mint> a, vector<mint> b) {
  vector<mint> res(size(a) + size(b) - 1);
  for (int i = 0; i < int(size(a)); i++) {
    if (a[i] == mint(0)) continue; 
    for (int j = 0; j < int(size(b)); j++) {
      res[i + j] = res[i + j] + a[i] * b[j];
    }
  }
  return res;
}

template <class mint>
vector<mint> convolution_ntt(vector<mint> a, vector<mint> b) {
  int n = a.size();
  int m = b.size();
  if (min(n, m) <= 60) return convolution_naive(a, b);
  int le = 1;
  while (le < n + m - 1) le = le * 2;
  a.resize(le), b.resize(le);
  ntt(a, 0), ntt(b, 0);
  for (int i = 0; i < le; i++) a[i] *= b[i];
  ntt(a, 1);
  a.resize(n + m - 1);
  return a;
}

template <class mint>
vector<mint> convolution(vector<mint> a, vector<mint> b) {
  return convolution_ntt(a, b);
}

template <class mint>
vector<mint> fps_inv(vector<mint> f, int deg = -1) {
  assert (f[0] != mint(0));
  if (deg == -1) deg = int(f.size());
  f.resize(deg);
  int n = int(f.size());
  // ntt prime
  if (mint::ntt_info().first != -1) {
    vector<mint> g(deg, mint(0));
    g[0] = f[0].inverse();
    int le = 1;
    while (le < deg) {
      vector<mint> a(2 * le, mint(0)), b(2 * le, mint(0));
      for (int i = 0; i < min(n, 2 * le); i++) {
        a[i] = f[i];
      }
      for (int i = 0; i < le; i++) {
        b[i] = g[i];
      }
      ntt(a, 0), ntt(b, 0);
      for (int i = 0; i < 2 * le; i++) {
        a[i] *= b[i];
      }
      ntt(a, 1);
      for (int i = 0; i < le; i++) {
        a[i] = mint(0);
      }
      ntt(a, 0);
      for (int i = 0; i < 2 * le; i++) {
        a[i] *= b[i];
      }
      ntt(a, 1);
      for (int i = le; i < min(deg, 2 * le); i++) {
        g[i] = -a[i];
      }
      le *= 2;
    }
    return g;
  }
  // not ntt prime
  // doubling
  else {
    vector<mint> g = {f[0].inverse()};
    vector<mint> gg(0);
    int le = 1;
    while (le < deg) {
      gg = convolution(g, g);
      gg.resize(2 * le);
      vector<mint> ff = {f.begin(), f.begin() + min(2 * le, n)};
      gg = convolution(gg, f);
      g.resize(2 * le);
      for (int i = 0; i < 2 * le; i++) {
        g[i] = g[i] + g[i] - gg[i];
      }
      le *= 2;
    }
    g.resize(deg);
    return g;
  }
}

template <class mint>
vector<mint> fps_exp(vector<mint> f, int deg = -1) {
  if (deg == -1) deg = int(f.size());
  f.resize(deg);
  int n = int(f.size());
  assert (n > 0);
  assert (f[0] == mint(0));
  // ntt prime
  if (mint::ntt_info().first != -1) {
    vector<mint> g = {mint(1), mint(0)};
    if (f.size() > 1) g[1] = f[1];
    vector<mint> h = {mint(1)};
    vector<mint> p, q;
    q = {mint(1), mint(1)};
    int le = 2;
    while (le < deg) {
      vector<mint> y = g;
      y.resize(2 * le);
      ntt(y, 0);
      p = q;
      vector<mint> z(le);
      for (int i = 0; i < le; i++) {
        z[i] = y[i] * p[i];
      }
      ntt(z, 1);
      for (int i = 0; i < le / 2; i++) {
        z[i] = mint(0);
      }
      ntt(z, 0);
      for (int i = 0; i < int(p.size()); i++) {
        z[i] = z[i] * (-p[i]);
      }
      ntt(z, 1);
      for (int i = le / 2; i < le; i++) {
        h.push_back(z[i]);
      }
      q = h;
      q.resize(2 * le);
      ntt(q, 0);

      vector<mint> x(le, mint(0));
      for (int i = 0; i < le - 1; i++) {
        x[i] = f[i + 1] * mint(i + 1);
      }
      ntt(x, 0);
      for (int i = 0; i < le; i++) {
        x[i] *= y[i];
      }
      ntt(x, 1);

      for (int i = 0; i < le - 1; i++) {
        x[i] -= g[i + 1] * mint(i + 1);
      }

      x.resize(2 * le);
      for (int i = 0; i < le - 1; i++) {
        x[i + le] = x[i], x[i] = mint(0);
      }
      ntt(x, 0);
      for (int i = 0; i < 2 * le; i++) {
        x[i] *= q[i];
      }
      ntt(x, 1);
      for (int i = int(x.size()) - 2; i >= 0; i--) {
        x[i + 1] = x[i] * mint(i + 1).inverse();
      }
      for (int i = 0; i < le; i++) {
        x[i] = mint(0);
      }
      for (int i = le; i < 2 * le; i++) {
        x[i] += f[i];
      }
      ntt(x, 0);
      for (int i = 0; i < 2 * le; i++) {
        x[i] *= y[i];
      }
      ntt(x, 1);
      for (int i = le; i < int(x.size()); i++) {
        g.push_back(x[i]);
      }
      le *= 2;
    }
    g.resize(deg);
    return g;
  }
  // not ntt prime
  // Newton's method
  else {
    int log = 0;
    while ((1 << log) < deg) log++;
    f.resize(1 << log);
    vector<mint> df(1 << log, mint(0));
    for (int i = 1; i < (1 << log); i++) {
      df[i - 1] = f[i] * mint(i);
    }
    vector<mint> g = {mint(1)}, h = {mint(1)};
    int le = 1;
    vector<mint> p;
    for (int _ = 0; _ < log; _++) {
      p = convolution(g, h);
      p.resize(le);
      p = convolution(p, h);
      p.resize(le);
      h.resize(le);
      for (int i = 0; i < le; i++) {
        h[i] += h[i] - p[i];
      }
      p = {df.begin(), df.begin() + le - 1};
      p = convolution(g, p);
      p.resize(2 * le - 1);
      for (int i = 0; i < 2 * le - 1; i++) {
        p[i] = -p[i];
      }
      for (int i = 0; i < le - 1; i++) {
        p[i] += g[i + 1] * mint(i + 1);
      }
      p = convolution(p, h);
      p.resize(2 * le - 1);
      for (int i = 0; i < le - 1; i++) {
        p[i] += df[i];
      }
      p.push_back(mint(0));
      for (int i = 2 * le - 2; i >= 0; i--) {
        p[i + 1] = p[i] * mint(i + 1).inverse();
      }
      p[0] = mint(0);
      for (int i = 0; i < 2 * le; i++) {
        p[i] = f[i] - p[i];
      }
      p[0] = mint(1);
      g = convolution(g, p);
      g.resize(2 * le);
      le *= 2;
    }
    g.resize(deg);
    return g;
  }
}

template <class mint>
vector<mint> fps_log(vector<mint> f, int deg = -1) {
  if (deg == -1) deg = int(f.size());
  f.resize(deg);
  int n = int(f.size());
  assert (n > 0);
  assert (f[0] == mint(1));
  vector<mint> df(deg, mint(0));
  for (int i = 1; i < min(deg + 1, n); i++) {
    df[i - 1] = f[i] * mint(i);
  }
  vector<mint> f_inv = fps_inv(f, deg);
  vector<mint> g = convolution(df, f_inv);
  g.resize(deg);
  for (int i = deg - 2; i >= 0; i--) {
    g[i + 1] = g[i] * mint(i + 1).inverse();
  }
  g[0] = mint(0);
  return g;
}

template <class mint>
vector<mint> fps_pow(vector<mint> f, long long k, int deg = -1) {
  if (deg == -1) deg = int(f.size());
  if (k == 0) {
    vector<mint> g(deg, mint(0));
    g[0] = mint(1);
    return g;
  }
  f.resize(deg);
  int d = 0;
  long long kk = 0; // overflow対策
  while (d < deg) {
    if (f[d] != mint(0)) break;
    d++;
    kk += k;
    if (kk >= deg) {
      vector<mint> g(deg, mint(0));
      return g;
    }
  }
  if (d == deg) {
    vector<mint> g(deg, mint(0));
    return g;
  }
  int dk = kk;
  mint a = f[d];
  mint a_inv = a.inverse();
  vector<mint> g(deg - dk, mint(0));
  for (int i = 0; i < deg - dk; i++) {
    g[i] = f[i + d] * a_inv;
  }
  g = fps_log(g);
  for (int i = 0; i < deg - dk; i++) {
    g[i] *= mint(k);
  }
  g = fps_exp(g);
  a = a.pow(k);
  vector<mint> res(deg, mint(0));
  for (int i = 0; i < deg - dk; i++) {
    res[i + dk] = g[i] * a;
  }
  return res;
}

template <class mint>
mint Bostan_Mori(vector<mint> P, vector<mint> Q, long long N) {
  while (N) {
    vector<mint> QQ = {Q.begin(), Q.end()};
    for (int i = 1; i < int(Q.size()); i += 2) QQ[i] = -QQ[i];
    P = convolution(P, QQ), Q = convolution(Q, QQ);
    vector<mint> S((P.size() + 1) / 2, mint(0)), T((Q.size() + 1) / 2, mint(0));
    int r = N % 2;
    for (int i = r; i < int(P.size()); i += 2) {
      S[i / 2] += P[i];
    }
    for (int i = 0; i < int(Q.size()); i += 2) T[i / 2] = Q[i];
    P = S, Q = T;
    N /= 2;
  }
  return P[0];
}

using mint = modint<998244353>;
using poly = vector<mint>;

int main() {
  long long N, K;
  cin >> N >> K;
  string S;
  cin >> S;
  if (N == K) {
    cout << 1 << endl;
    return 0;
  }
  long long r = 0;
  for (int i = 0; i < K; i++) {
    if (S[i] == '(') r++;
    else break;
  }
  for (int i = K - 1; i >= 0; i--) {
    if (S[i] == ')') r++;
    else break;
  }
  if (r == K) {
  // S = ((...()...))のとき
    vector<mint> f = {mint(1), -mint(1)};
    f = fps_pow(f, K, K + 1);
    f = convolution(f, {mint(1), -mint(2)});
    mint ans = Bostan_Mori({mint(1)}, f, N - K);
    cout << ans.get() << endl;
    return 0;
  }
  r += 2;
  mint ans = mint(1);
  for (int i = 1; i <= r - 1; i++) {
    ans *= mint(N - K + i) / mint(i);
  }
  cout << ans.get() << endl;
}
yukicoder

結果

ソースコード
