結果

問題 No.2498 OX Operations
ユーザー KumaTachiRenKumaTachiRen
提出日時 2023-09-04 12:19:13
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 197 ms / 4,000 ms
コード長 3,043 bytes
コンパイル時間 6,371 ms
コンパイル使用メモリ 266,444 KB
実行使用メモリ 5,524 KB
最終ジャッジ日時 2023-09-04 12:19:25
合計ジャッジ時間 10,853 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,360 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 2 ms
4,360 KB
testcase_03 AC 2 ms
4,356 KB
testcase_04 AC 2 ms
4,356 KB
testcase_05 AC 2 ms
4,356 KB
testcase_06 AC 1 ms
4,356 KB
testcase_07 AC 1 ms
4,356 KB
testcase_08 AC 2 ms
4,356 KB
testcase_09 AC 1 ms
4,356 KB
testcase_10 AC 1 ms
4,356 KB
testcase_11 AC 2 ms
4,356 KB
testcase_12 AC 2 ms
4,352 KB
testcase_13 AC 3 ms
4,360 KB
testcase_14 AC 3 ms
4,356 KB
testcase_15 AC 135 ms
5,404 KB
testcase_16 AC 173 ms
5,460 KB
testcase_17 AC 112 ms
5,448 KB
testcase_18 AC 163 ms
5,524 KB
testcase_19 AC 144 ms
5,404 KB
testcase_20 AC 172 ms
5,452 KB
testcase_21 AC 189 ms
5,512 KB
testcase_22 AC 95 ms
4,356 KB
testcase_23 AC 85 ms
4,356 KB
testcase_24 AC 193 ms
5,460 KB
testcase_25 AC 192 ms
5,444 KB
testcase_26 AC 197 ms
5,412 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using namespace atcoder;

struct Fast {
  Fast() {
    std::cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << setprecision(10);
  }
} fast;

#define rep(i, a, b) for (int(i) = (a); (i) < (int)(b); (i)++)
#define rrep(i, a, b) for (int(i) = (int)(b)-1; (i) >= (int)(a); (i)--)

template <class F, F (*composition)(F, F), F (*id)()>
struct dual_segtree {
 public:
  dual_segtree(int n) {
    while (sz < n) {
      sz <<= 1;
      log++;
    }
    lz = vector<F>(sz * 2, id());
  }
  F get(int p) {
    p += sz;
    for (int i = log; i > 0; i--) push(p >> i);
    return lz[p];
  }
  void set(int p, const F& f) {
    p += sz;
    for (int i = log; i > 0; i--) push(p >> i);
    lz[p] = f;
  }
  void apply(int l, int r, const F& f) {
    if (l >= r) return;
    l += sz;
    r += sz;
    for (int i = log; i > 0; i--) {
      if (((l >> i) << i) != l) push(l >> i);
      if (((r >> i) << i) != r) push((r - 1) >> i);
    }
    for (; l < r; l /= 2, r /= 2) {
      if (l & 1) comp(lz[l++], f);
      if (r & 1) comp(lz[--r], f);
    }
  }

 private:
  int sz = 1, log = 0;
  vector<F> lz;
  void comp(F& f, const F& g) {
    f = composition(g, f);
  }
  void push(int p) {
    comp(lz[p * 2], lz[p]);
    comp(lz[p * 2 + 1], lz[p]);
    lz[p] = id();
  }
};

const int LOG = 30;
const int MASK = (1 << LOG) - 1;
using P = pair<int, int>;
using mint = modint998244353;

P composition(P f, P g) {
  return P((~g.first & f.first) | (g.first & f.second), (~g.second & f.first) | (g.second & f.second));
};
P id() { return P(0, MASK); }

int main() {
  int n, q;
  cin >> n >> q;
  vector<int> m(n);
  rep(i, 0, n) cin >> m[i];
  dual_segtree<P, composition, id> seg(n);

  while (q--) {
    char c;
    int l, r, x;
    cin >> c >> l >> r >> x;
    l--;
    seg.apply(l, r, c == 'o' ? P(x, MASK) : P(x, MASK ^ x));
  }

  vector<mint> fact(100), ifact(100);
  fact[0] = 1;
  rep(i, 1, fact.size()) fact[i] = fact[i - 1] * i;
  ifact[99] = fact[99].inv();
  rrep(i, 1, ifact.size()) ifact[i - 1] = ifact[i] * i;
  auto binom = [fact, ifact](int n, int k) -> mint {
    return k < 0 || k > n ? 0 : fact[n] * ifact[k] * ifact[n - k];
  };

  vector<mint> prod(LOG + 1, 1);
  auto solve_small = [&prod, binom](int b, int c, int m) -> void {
    vector<mint> f(LOG + 1, 0);
    auto cnt = array<int, 3>{0, 0, 0};
    int a = __builtin_popcount(((m ^ MASK) & b) | (m & c));
    rep(i, 0, LOG) {
      a -= (((m ^ MASK) & b) | (m & c)) & 1;
      a += b & 1;
      if (m & 1) {
        rep(j, 0, LOG + 1) {
          f[j] += binom(cnt[1], j - a - cnt[2]) * (1 << (cnt[0] + cnt[2]));
        }
      }
      a -= b & 1;
      cnt[(b & 1) + (c & 1)]++;
      m >>= 1;
      b >>= 1;
      c >>= 1;
    }
    rep(i, 0, LOG) f[i + 1] += f[i];
    rep(i, 0, LOG + 1) prod[i] *= f[i];
  };

  rep(i, 0, n) {
    auto p = seg.get(i);
    solve_small(p.first, p.second, m[i] + 1);
  }

  mint ans = LOG * prod[LOG];
  rep(i, 0, LOG) ans -= prod[i];
  cout << ans.val() << endl;
}
0