convolution/test/hadamard_xor.test.cpp

• View this file on GitHub
• Last update: 2024-09-22 16:07:49+09:00
• Problem: https://yukicoder.me/problems/no/1240

Depends on

• convolution/hadamard.hpp

Code

#include "../hadamard.hpp"
#define PROBLEM "https://yukicoder.me/problems/no/1240"
#include <iostream>
using namespace std;

int main() {
    cin.tie(nullptr), ios::sync_with_stdio(false);

    int N, X;
    cin >> N >> X;
    vector<int> A(N);
    for (auto &x : A) { cin >> x; }
    const int D = 18;
    vector<long long> cnt(1 << D);
    for (auto a : A) cnt[a]++;
    cnt = xorconv(cnt, cnt);
    cnt[0] -= N;
    long long ret = 0;

    for (int d = 0; d < D; d++) {
        vector<long long> cntd(1 << D);
        int nd = 0;
        for (auto a : A)
            if (((a >> d) & 1) == 0) { cntd[a]++, nd++; }
        cntd = xorconv(cntd, cntd);
        cntd[0] -= nd;
        for (int i = 0; i < X; i++) { ret += (1LL << d) * (cnt[i] - cntd[i]) / 2; }
    }
    cout << ret << '\n';
}

#line 2 "convolution/hadamard.hpp"
#include <cassert>
#include <vector>

// Fast Walsh-Hadamard transform and its abstraction
// Tutorials: <https://codeforces.com/blog/entry/71899>
//            <https://csacademy.com/blog/fast-fourier-transform-and-variations-of-it>
template <typename T, typename F> void abstract_fwht(std::vector<T> &seq, F f) {
    const int n = seq.size();
    assert(__builtin_popcount(n) == 1);
    for (int w = 1; w < n; w *= 2) {
        for (int i = 0; i < n; i += w * 2) {
            for (int j = 0; j < w; j++) f(seq.at(i + j), seq.at(i + j + w));
        }
    }
}

template <typename T, typename F1, typename F2>
std::vector<T> bitwise_conv(std::vector<T> x, std::vector<T> y, F1 f, F2 finv) {
    const int n = x.size();
    assert(__builtin_popcount(n) == 1);
    assert(x.size() == y.size());
    if (x == y) {
        abstract_fwht(x, f), y = x;
    } else {
        abstract_fwht(x, f), abstract_fwht(y, f);
    }
    for (int i = 0; i < (int)x.size(); i++) x.at(i) *= y.at(i);
    abstract_fwht(x, finv);
    return x;
}

// bitwise xor convolution (FWHT-based)
// ret[i] = \sum_j x[j] * y[i ^ j]
// if T is integer, ||x||_1 * ||y||_1 * 2 < numeric_limits<T>::max()
template <typename T> std::vector<T> xorconv(std::vector<T> x, std::vector<T> y) {
    auto f = [](T &lo, T &hi) {
        T c = lo + hi;
        hi = lo - hi, lo = c;
    };
    auto finv = [](T &lo, T &hi) {
        T c = lo + hi;
        hi = (lo - hi) / 2,
        lo = c / 2; // Reconsider HEAVY complexity of division by 2 when T is ModInt
    };
    return bitwise_conv(x, y, f, finv);
}

// bitwise AND conolution
// ret[i] = \sum_{(j & k) == i} x[j] * y[k]
template <typename T> std::vector<T> andconv(std::vector<T> x, std::vector<T> y) {
    return bitwise_conv(x, y, [](T &lo, T &hi) { lo += hi; }, [](T &lo, T &hi) { lo -= hi; });
}

// bitwise OR convolution
// ret[i] = \sum_{(j | k) == i} x[j] * y[k]
template <typename T> std::vector<T> orconv(std::vector<T> x, std::vector<T> y) {
    return bitwise_conv(x, y, [](T &lo, T &hi) { hi += lo; }, [](T &lo, T &hi) { hi -= lo; });
}
#line 2 "convolution/test/hadamard_xor.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/1240"
#include <iostream>
using namespace std;

int main() {
    cin.tie(nullptr), ios::sync_with_stdio(false);

    int N, X;
    cin >> N >> X;
    vector<int> A(N);
    for (auto &x : A) { cin >> x; }
    const int D = 18;
    vector<long long> cnt(1 << D);
    for (auto a : A) cnt[a]++;
    cnt = xorconv(cnt, cnt);
    cnt[0] -= N;
    long long ret = 0;

    for (int d = 0; d < D; d++) {
        vector<long long> cntd(1 << D);
        int nd = 0;
        for (auto a : A)
            if (((a >> d) & 1) == 0) { cntd[a]++, nd++; }
        cntd = xorconv(cntd, cntd);
        cntd[0] -= nd;
        for (int i = 0; i < X; i++) { ret += (1LL << d) * (cnt[i] - cntd[i]) / 2; }
    }
    cout << ret << '\n';
}

Back to top page