結果

問題 No.2990 Interval XOR
コンテスト
ユーザー akakimidori
提出日時 2024-05-31 05:12:50
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 508 ms / 2,000 ms
コード長 3,525 bytes
コンパイル時間 1,655 ms
コンパイル使用メモリ 117,096 KB
実行使用メモリ 18,676 KB
最終ジャッジ日時 2024-12-14 23:30:39
合計ジャッジ時間 11,360 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <array>

#include <atcoder/modint>

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) {
    if (std::find(p.begin(), p.end(), std::make_pair(0, 1 << n)) != p.end()) {
        const mint prod = std::accumulate(p.begin(), p.end(), mint(1), [&](mint a, auto p) {
            return a * (p.second - p.first);
        }) / (1 << n);
        return std::vector<mint>(1 << n, prod);
    }
    std::vector<mint> ans(1 << n);
    std::vector<std::pair<int, int>> q = p;
    REP(i, 0, n) {
        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 = r == (1 << n) ? 0 : (l ^ r) >> (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 + (r >> i & 1)] += r - t;
            }
            if (s < t && (t >> i & 1) == 1) {
                t -= 1 << i;
                y[up] += 1 << i;
            }
            fwht(y.data(), 4);
            const int x = 4 * pos;
            REP(k, 0, 4) dp[x + k] *= y[k];
        }
        for (int size = 2; 2 * size < (int)dp.size(); size <<= 1) {
            for (auto po = dp.begin(); po != dp.end(); po += 4 * size) {
                for (auto a = po, b = po + size, c = b + size, d = c + size; a != po + size; ++a, ++b, ++c, ++d) {
                    const mint x = *a;
                    const mint y = *b;
                    const mint z = *c;
                    const mint w = *d;
                    *a = x * z;
                    *b = x * w;
                    *c = y * w;
                    *d = 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