#1157760 (C++23) No.3500 01 String

• 問題: No.3500 01 String
• ユーザー: KowerKoint2010
• 提出日時: 2026-04-17 20:39:50
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 268 ms / 2,000 ms
• コード長: 5,484 bytes
• コンパイル時間: 2,598 ms
• コンパイル使用メモリ: 344,796 KB
• 実行使用メモリ: 12,504 KB
• 最終ジャッジ日時: 2026-04-17 20:40:28
• 合計ジャッジ時間: 6,524 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_1

ファイルパターン	結果
sample	AC * 3
other	AC * 20

ソースコード

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1ll << 60;
#define REP(i, n) for(ll i =0; i < ll(n); i++)
template <class T> using V = vector<T>;
template <class A, class B>
bool chmax(A& a, B b) { return a<b && (a=b, true); }
template <class A, class B>
bool chmin(A& a, B b) { return b<a && (a=b, true); }

template <int MD, int g = 3>
struct ModInt {
  using M = ModInt;
  const static inline M G = g;
  unsigned int v;
  ModInt() : v(0) {}
  ModInt(ll w) : v(w % MD + MD) {
    if(v >= MD) v -= MD;
  }
  static M raw(unsigned int v) {
    M res;
    res.v = (v < MD) ? v : v - MD;
    return res;
  }
  explicit operator bool() const {
    return v != 0;
  }
  M operator-() const {
    return M() - *this;
  }
  M operator+(M r) const {
    return raw(v + r.v);
  }
  M operator-(M r) const {
    return raw(v + MD - r.v);
  }
  M operator*(M r) const {
    return raw(ll(v) * r.v % MD);
  }
  M operator/(M r) const {
    return *this * r.inv();
  }
  M& operator+=(M r) {
    return *this = *this + r;
  }
  M& operator-=(M r) {
    return *this = *this - r;
  }
  M& operator*=(M r) {
    return *this = *this * r;
  }
  M& operator/=(M r) {
    return *this = *this / r;
  }
  bool operator==(M r) const {
    return v == r.v;
  }
  M pow(ll n) const {
    M x = *this, r = 1;
    while (n) {
      if (n & 1) r *= x;
      x *= x;
      n >>= 1;
    }
    return r;
  }
  M inv() const {
    return pow(MD - 2);
  }
  friend ostream& operator<<(ostream& os, M r) {
    return os << r.v;
  }
};
// using Mint = ModInt<998244353, 3>;

template <class S, class F, S op(S, S),
          F composition(F, F), S mapping(F, S)>
struct LazySegtree {
  int n, s, log;
  S e;
  F id;
  V<S> d;
  V<F> lz;

  void update(int k) {
    d[k] = op(d[2 * k], d[2 * k + 1]);
  }
  void all_apply(int k, F f) {
    d[k] = mapping(f, d[k]);
    if (k < s) lz[k] = composition(f, lz[k]);
    // if(d[k].fail) push(k), update(k);
  }
  void push(int k) {
    all_apply(2 * k, lz[k]);
    all_apply(2 * k + 1, lz[k]);
    lz[k] = id;
  }
  
  LazySegtree() = default;
  LazySegtree(unsigned n, S e, F id)
      : n(n), s(bit_ceil(n)), e(e), id(id) {
    log = countr_zero((unsigned)s);
    d.assign(2 * s, e), lz.assign(s, id);
  }
  LazySegtree(const vector<S>& v, S e, F id)
      : LazySegtree(v.size(), e, id) {
    ranges::copy(v, d.begin() + s);
    for (int i = s - 1; i >= 1; i--) update(i);
  }
  void set(int p, S x) {
    p += s;
    for (int i = log; i >= 1; i--) push(p >> i);
    d[p] = x;
    for (int i = 1; i <= log; i++) update(p >> i);
  }
  S get(int p) {
    p += s;
    for (int i = log; i >= 1; i--) push(p >> i);
    return d[p];
  }
  S prod(int l, int r) {
    if (l == r) return e;
    l += s, r += s;
    for (int i = log; i >= 1; i--) {
      if (((l >> i) << i) != l) push(l >> i);
      if (((r >> i) << i) != r) push((r - 1) >> i);
    }
    S sml = e, smr = e;
    while (l < r) {
      if (l & 1) sml = op(sml, d[l++]);
      if (r & 1) smr = op(d[--r], smr);
      l >>= 1, r >>= 1;
    }
    return op(sml, smr);
  }
  void apply(int l, int r, F f) {
    if (l == r) return;
    l += s, r += s;
    for (int i = log; i >= 1; i--) {
      if (((l >> i) << i) != l) push(l >> i);
      if (((r >> i) << i) != r) push((r - 1) >> i);
    }
    {
      int l2 = l, r2 = r;
      while (l < r) {
        if (l & 1) all_apply(l++, f);
        if (r & 1) all_apply(--r, f);
        l >>= 1, r >>= 1;
      }
      l = l2, r = r2;
    }
    for (int i = 1; i <= log; i++) {
      if (((l >> i) << i) != l) update(l >> i);
      if (((r >> i) << i) != r) update((r - 1) >> i);
    }
  }
  template <class G>
  int max_right(int l, G g) {
    if (l == n) return n;
    l += s;
    for (int i = log; i >= 1; i--) push(l >> i);
    S sm = e;
    do {
      while (l % 2 == 0) l >>= 1;
      if (!g(op(sm, d[l]))) {
        while (l < s) {
          push(l);
          l = 2 * l;
          if (g(op(sm, d[l]))) {
            sm = op(sm, d[l]);
            l++;
          }
        }
        return l - s;
      }
      sm = op(sm, d[l]);
      l++;
    } while ((l & -l) != l);
    return n;
  }
  template <bool (*g)(S)>
  int min_left(int r) {
    return min_left(r, [](S x) { return g(x); });
  }
  template <class G>
  int min_left(int r, G g) {
    if (r == 0) return 0;
    r += s;
    for (int i = log; i >= 1; i--) push((r - 1) >> i);
    S sm = e;
    do {
      r--;
      while (r > 1 && (r % 2)) r >>= 1;
      if (!g(op(d[r], sm))) {
        while (r < s) {
          push(r);
          r = 2 * r + 1;
          if (g(op(d[r], sm))) {
            sm = op(d[r], sm);
            r--;
          }
        }
        return r + 1 - s;
      }
      sm = op(d[r], sm);
    } while ((r & -r) != r);
    return 0;
  }
};

using MI = ModInt<998244353>;
MI addm(MI a, MI b) { return a+b; }

void testcase() {
  int n; cin >> n;
  string a; cin >> a;
  V<V<int>> pos(2);
  REP(i, n) pos[a[i]-'0'].push_back(i);
  LazySegtree<MI, MI, addm, addm, addm> seg(n+1, MI(0), MI(0));
  seg.set(0, 1);
  REP(i, n) {
    if(a[i] == '0') {
      auto nxt = ranges::lower_bound(pos[0], i+1);
      int r = (nxt == pos[0].end() ? n+1 : *nxt+1);
      seg.apply(i+1, r, seg.get(i));
    } else {
      auto it = ranges::lower_bound(pos[1], i);
      int l = (it == pos[1].begin() ? 0 : *(it-1)+1);
      seg.apply(i+1, i+2, seg.prod(l, i+1));
    }
  }
  cout << seg.get(n) << '\n';
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  testcase();
}