#1191247 (C++23) No.3753 Certainly a Cretan

• 問題: No.3753 Certainly a Cretan
• ユーザー: Kude
• 提出日時: 2026-10-02 23:40:01
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 166 ms / 2,500 ms
• コード長: 3,538 bytes
• コンパイル時間: 2,289 ms
• コンパイル使用メモリ: 362,780 KB
• 実行使用メモリ: 35,444 KB
• 最終ジャッジ日時: 2026-10-02 23:40:15
• 合計ジャッジ時間: 6,622 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge4_0

ファイルパターン	結果
sample	AC * 2
other	AC * 46

コンパイルメッセージ

main.cpp:49:6: warning: '{anonymous}::mint {anonymous}::perm(int, int)' defined but not used [-Wunused-function]
   49 | mint perm(int n, int k) {
      |      ^~~~
main.cpp:48:6: warning: '{anonymous}::mint {anonymous}::fact(int)' defined but not used [-Wunused-function]
   48 | mint fact(int n) {return Fact[n];}
      |      ^~~~
main.cpp:44:6: warning: '{anonymous}::mint {anonymous}::icomb(int, int)' defined but not used [-Wunused-function]
   44 | mint icomb(int n, int k) {
      |      ^~~~~

ソースコード

#include<bits/stdc++.h>
namespace {
#pragma GCC diagnostic ignored "-Wunused-function"
#include<atcoder/all>
#pragma GCC diagnostic warning "-Wunused-function"
using namespace std;
using namespace atcoder;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(i,n) for(int i = (int)(n) - 1; i >= 0; i--)
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; }
template<class T> bool chmin(T& a, const T& b) { if (b < a) { a = b; return true; } else return false; }
using ll = long long;
using P = pair<int,int>;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<ll>;
using VVL = vector<VL>;
using mint = modint998244353;

constexpr int FACT_SIZE = 1000000;
mint Fact[FACT_SIZE + 1];
mint iFact[FACT_SIZE + 1];
const auto fact_init = [] {
    Fact[0] = mint::raw(1);
    for(int i = 1; i <= FACT_SIZE; ++i) {
        Fact[i] = Fact[i-1] * i;
    }
    iFact[FACT_SIZE] = Fact[FACT_SIZE].inv();
    for(int i = FACT_SIZE; i; --i) {
        iFact[i-1] = iFact[i] * i;
    }
    return false;
}();

mint comb(int n, int k) {
    if (k == 0) return mint::raw(1);
    assert(n >= 0 && k >= 0);
    if (k > n) return mint::raw(0);
    return Fact[n] * iFact[n - k] * iFact[k];
}

mint icomb(int n, int k) {
    return iFact[n] * Fact[n - k] * Fact[k];
}

mint fact(int n) {return Fact[n];}
mint perm(int n, int k) {
    assert(0 <= n);
    return Fact[n] * iFact[n - k];
}

mint cat(int d) {
  mint ans = comb(2*d, d);
  if (d) ans -= comb(2*d, d-1);
  return ans;
}

} int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, q;
  cin >> n >> q;
  string s;
  cin >> s;
  set<int> cuts{0};
  for (int i = 1; i < n; i++) if (s[i-1] != s[i]) cuts.emplace(i);
  mint ans = 1;
  int odds = 0;
  auto add = [&](int d) {
    if (d % 2 == 0) ans *= cat(d/2);
    else odds++;
  };
  auto rmv = [&](int d) {
    if (d % 2 == 0) ans /= cat(d/2);
    else odds--;
  };
  for (auto it1 = cuts.begin(), it2 = next(it1); it2 != cuts.end(); it1 = it2++) {
    add(*it2 - *it1);
  }
  auto flip = [&](int i) {
    if (s[i-1] == s[i]) {
      auto it = cuts.insert(i).first;
      auto pit = prev(it), nit = next(it);
      if (nit != cuts.end()) rmv(*nit - *pit), add(*nit - *it);
      add(*it - *pit);
    } else {
      auto it = cuts.find(i);
      auto pit = prev(it), nit = next(it);
      rmv(*it - *pit);
      if (nit != cuts.end()) rmv(*nit - *it), add(*nit - *pit);
      cuts.erase(it);
    }
  };
  rep(_, q) {
    int op;
    cin >> op;
    if (op == 1) {
      int i;
      cin >> i;
      i--;
      if (i) flip(i);
      if (i+1 < n) flip(i+1);
      s[i] ^= 'N' ^ 'Y';
    } else {
      int k;
      cin >> k;
      int last = *cuts.rbegin();
      if (odds) {
        cout << 0 << '\n';
        continue;
      }
      int vlast = k - (n - k);
      // add+sub = n-last
      // add-sub = vlast
      int add = (n - last + vlast) / 2;
      int sub = (n - last - vlast) / 2;
      if (add < 0 || sub < 0) {
        cout << 0 << '\n';
        continue;
      }
      mint res;
      if (s[last] == 'N') {
        if (vlast >= 0) {
          mint mul = comb(add + sub, sub);
          if (sub) mul -= comb(add + sub, sub - 1);
          res = ans * mul;
        }
      } else {
        if (vlast <= 0) {
          mint mul = comb(add + sub, add);
          if (add) mul -= comb(add + sub, add - 1);
          res = ans * mul;
        }
      }
      cout << res.val() << '\n';
    }
  }
}