結果

問題 No.2990 Interval XOR
コンテスト
ユーザー akakimidori
提出日時 2024-06-02 10:36:58
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 531 ms / 2,000 ms
コード長 3,180 bytes
コンパイル時間 1,250 ms
コンパイル使用メモリ 120,416 KB
実行使用メモリ 18,632 KB
最終ジャッジ日時 2024-12-14 23:31:43
合計ジャッジ時間 9,829 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <algorithm>
#include <array>
#include <atcoder/modint>
#include <cassert>
#include <iostream>
#include <vector>
#include <tuple>

using mint = atcoder::modint998244353;

#define REP(i, s, t) for (int i = (s); i < (t); ++i)

template <class T>
T read() {
    T v;
    std::cin >> v;
    return v;
}

template <class T>
void fwht(T *a, int n) {
    assert(n > 0 && (n & (n - 1)) == 0);
    for (int w = 1; w < n; w <<= 1) {
        for (auto s = a; s != a + n; s += 2 * w) {
            for (auto x = s, y = s + w; x != s + w; ++x, ++y) {
                const T p = *x;
                const T q = *y;
                *x = p + q;
                *y = p - q;
            }
        }
    }
}

std::vector<mint> solve(const int n, const int m, const std::vector<std::pair<int, int>> &p) {
    std::vector<mint> ans(1 << n);
    std::vector<std::pair<int, int>> q = p;
    REP(i, 0, n + 1) {
        std::vector<mint> dp(1 << (n + 1 - i), 1);
        int base = 0;
        REP(j, 0, m) {
            const auto [l, r] = p[j];
            auto &[s, t] = q[j];
            base ^= l & ~((2 << i) - 1);
            const int pos = (l ^ (r - 1)) >> (i + 1);
            std::array<mint, 4> y{0, 0, 0, 0};
            if (l < s) {
                y[l >> i & 1] += s - l;
            }
            if (s < t && (s >> i & 1) == 1) {
                y[1] += 1 << i;
                s += 1 << i;
            }
            const int up = pos > 0 ? 2 : 0;
            if (t < r) {
                y[up + (t >> i & 1)] += r - t;
            }
            if (s < t && (t >> i & 1) == 1) {
                t -= 1 << i;
                y[up] += 1 << i;
            }
            const int len = pos > 0 ? 4 : 2;
            fwht(y.data(), len);
            const int x = 4 * pos;
            REP(k, 0, len) dp[x + k] *= y[k];
        }
        for (int size = 2; 2 * size < (int)dp.size(); size <<= 1) {
            for (auto a = dp.begin(); a != dp.end(); a += 4 * size) {
                REP(i, 0, size) {
                    mint &x = a[i];
                    mint &y = a[i + size];
                    mint &z = a[i + 2 * size];
                    mint &w = a[i + 3 * size];
                    std::tie(x, y, z, w) = std::make_tuple(x * z, x * w, y * w, y * z);
                }
            }
        }
        dp.resize(1 << (n - i), 0);
        fwht(dp.data(), dp.size());
        const mint inv = mint(1) / (1 << (n - i));
        const mint scat = mint(1) / (1 << i);
        REP(j, 0, (int)dp.size()) {
            const int s = base ^ (j << i);
            const int t = s + (1 << i);
            mint add = dp[j] * inv;
            REP(k, s, t) add -= ans[k];
            add *= scat;
            REP(k, s, t) ans[k] += add;
        }
    }
    return ans;
}

int main() {
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    const auto n = read<int>();
    const auto m = read<int>();
    std::vector<std::pair<int, int>> p(m);
    for (auto &q : p) {
        q.first = read<int>();
        q.second = read<int>() + 1;
    }
    const auto ans = solve(n, m, p);
    for (const auto x : ans) {
        std::cout << x.val() << "\n";
    }
    return 0;
}
0