結果

問題 No.2990 Interval XOR
ユーザー Kude
提出日時 2024-12-23 22:44:04
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 825 ms / 2,000 ms
コード長 4,549 bytes
コンパイル時間 4,887 ms
コンパイル使用メモリ 293,908 KB
実行使用メモリ 31,516 KB
最終ジャッジ日時 2024-12-23 22:44:22
合計ジャッジ時間 15,854 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;

struct S {
  mint v0, v1;
  friend S operator+(const S& lhs, const S& rhs) { return {lhs.v0 + rhs.v0, lhs.v1 + rhs.v1}; }
  friend S operator-(const S& lhs, const S& rhs) { return {lhs.v0 - rhs.v0, lhs.v1 - rhs.v1}; }
  friend S operator*(const S& lhs, const S& rhs) { return {lhs.v0 * rhs.v0 + lhs.v1 * rhs.v1, lhs.v0 * rhs.v1 + lhs.v1 * rhs.v0}; }
  bool is_zero() { return v0 == 0 && v1 == 0; }
  S& operator*=(const S& rhs) { return *this = *this * rhs; }
  S& operator-=(const S& rhs) { return *this = *this - rhs; }
  S& operator*=(mint v) { v0 *= v, v1 *= v; return *this; }
};
struct Factor {
  int x1, x2;
  S c1, c2;
};
struct ProdRes {
  int x0;
  vector<int> basis;
  vector<S> dist;
};

ProdRes two_term_poly_xor_product(const vector<Factor>& d) {
  using mint = S;
  vector<array<mint, 2>> dp{{S{1}, S{1}}};
  int x0 = 0;
  vector<int> basis;
  for (auto [x1, x2, c1, c2] : d) {
    if (c1.is_zero() || c2.is_zero()) {
      mint v;
      if (!c1.is_zero()) x0 ^= x1, v = c1;
      else if (!c2.is_zero()) x0 ^= x2, v = c2;
      else return ProdRes{0, {}, {S{}}};
      dp[0][0] *= v;
      dp[0][1] *= v;
      continue;
    }
    x0 ^= x1;
    int x = x1 ^ x2, choice = 0, k = 0;
    for (int b : basis) {
      if (chmin(x, x ^ b)) choice ^= 1 << k;
      k++;
    }
    if (x) {
      basis.emplace_back(x);
      choice ^= 1 << k;
      dp.resize(1 << size(basis), {S{1}, S{1}});
    }
    dp[choice][0] *= c1 + c2;
    dp[choice][1] *= c1 - c2;
  }
  int n2 = 1 << ssize(basis);
  for (int k2 = 1; k2 < n2; k2 *= 2) {
    for (int di = 2 * k2, i_high = 0; i_high < n2; i_high += di) {
      for (int i_low = 0; i_low < k2; i_low++) {
        int i0 = i_low | i_high, i1 = i0 | k2;
        auto d0 = dp[i0], d1 = dp[i1];
        dp[i0] = {d0[0] * d1[0], d0[1] * d1[1]};
        dp[i1] = {d0[0] * d1[1], d0[1] * d1[0]};
      }
    }
  }
  vector<mint> dist(n2);
  for (int i = 0; i < n2; i++) dist[i] = dp[i][0];
  for (int k2 = 1; k2 < n2; k2 *= 2) {
    for (int di = 2 * k2, i_high = 0; i_high < n2; i_high += di) {
      for (int i_low = 0; i_low < k2; i_low++) {
        int i0 = i_low | i_high, i1 = i0 | k2;
        auto v0 = dist[i0], v1 = dist[i1];
        dist[i0] = v0 + v1, dist[i1] = v0 - v1;
      }
    }
  }
  auto iz = atcoder::modint998244353(2).inv().pow(ssize(basis));
  for (int i = 0; i < n2; i++) dist[i] *= iz;
  return ProdRes{x0, move(basis), move(dist)};
}

} int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  int n2 = 1 << n;
  struct S { int l1, r1, l2, r2; };
  vector<S> d(m);
  vector<mint> dp(n2);
  dp[0] = 1;
  rep(i, m) {
    int l, r;
    cin >> l >> r;
    r++;
    int c = -bit_floor(1U * l ^ r) & r;
    d[i] = {l, c, c, r};
    dp[0] *= r - l;
  }
  const mint inv2 = mint(2).inv();
  rrep(k, n) {
    vector<Factor> fs(m);
    for (int i = 0; auto& [l1, r1, l2, r2] : d) {
      if (r1 - l1 >= 1 << (k + 1)) r1 -= 1 << (k + 1);
      if (r2 - l2 >= 1 << (k + 1)) l2 += 1 << (k + 1);
      int c1 = (l1 >> k | 1) << k, c2 = (l2 >> k | 1) << k;
      fs[i++] = {l1 >> (k + 1) << (k + 1), l2 >> (k + 1) << (k + 1), {min(r1, c1) - min(l1, c1), max(r1, c1) - max(l1, c1)}, {min(r2, c2) - min(l2, c2), max(r2, c2) - max(l2, c2)}};
    }
    auto [x0, basis, dist] = two_term_poly_xor_product(fs);
    int sz = ssize(basis);
    VI idx(1 << sz);
    rep(i, sz) idx[1 << i] = basis[i];
    rep(i, 1 << sz) {
      int j = i & -i;
      idx[i] = idx[j] ^ idx[i ^ j];
    }
    rep(i, 1 << sz) idx[i] ^= x0;
    rep(i, 1 << sz) dp[idx[i]] -= dist[i].v0 + dist[i].v1;
    for (int di = 1 << (k + 1), i = 0; i < n2; i += di) dp[i] *= inv2, dp[i | 1 << k] += dp[i];
    rep(i, 1 << sz) dp[idx[i]] += dist[i].v0, dp[idx[i] | 1 << k] += dist[i].v1;
  }
  for (auto x : dp) cout << x.val() << '\n';
}
0