library/bitwise/Xor.hpp

View this file on GitHub
Last update: 2025-11-24 18:49:07+09:00
Include: #include "library/bitwise/Xor.hpp"

Depends on

Verified with

test/library-checker/Convolution/BitwiseXorConvolution.test.cpp

Code

#pragma once
#include "library/bitwise/Util.hpp"
#define REP_(i, n) for (int i = 0; i < (n); i++)
#define RREP_(i, n) for (int i = (n) - 1; i >= 0; i--)
struct BitwiseXor {
    template <typename T> static void zeta(std::vector<T> &A) {
        const int n = bitwise::log2(A.size());
        REP_(i, n)
        REP_(S, 1 << n) {
            if (bitwise::in(S, i))
                continue;
            T x = A[S], y = A[S | (1 << i)];
            A[S] -= y;
            A[S | (1 << i)] += x;
        }
    }
    template <typename T> static void mobius(std::vector<T> &A) {
        const int n = bitwise::log2(A.size());
        RREP_(i, n)
        REP_(S, 1 << n) {
            if (bitwise::in(S, i))
                continue;
            T x = A[S], y = A[S | (1 << i)];
            A[S] += y;
            A[S | (1 << i)] -= x;
        }
        T inv = T(1) / (1 << n);
        REP (S, 1 << n)
            A[S] *= inv;
    }
    template <typename T>
    static std::vector<T> convolution(std::vector<T> A, std::vector<T> B) {
        zeta(A);
        zeta(B);
        REP (S, A.size())
            A[S] *= B[S];
        mobius(A);
        return A;
    }
};
#undef REP_
#undef RREP_

#line 2 "library/bitwise/Util.hpp"
namespace bitwise{
  static int log2(int N){
    int n=__builtin_ffs(N)-1;
    assert((1<<n)==N);
    return n;
  }
  static bool in(int S,int a){ return (S>>a)&1; }
}
#line 3 "library/bitwise/Xor.hpp"
#define REP_(i, n) for (int i = 0; i < (n); i++)
#define RREP_(i, n) for (int i = (n) - 1; i >= 0; i--)
struct BitwiseXor {
    template <typename T> static void zeta(std::vector<T> &A) {
        const int n = bitwise::log2(A.size());
        REP_(i, n)
        REP_(S, 1 << n) {
            if (bitwise::in(S, i))
                continue;
            T x = A[S], y = A[S | (1 << i)];
            A[S] -= y;
            A[S | (1 << i)] += x;
        }
    }
    template <typename T> static void mobius(std::vector<T> &A) {
        const int n = bitwise::log2(A.size());
        RREP_(i, n)
        REP_(S, 1 << n) {
            if (bitwise::in(S, i))
                continue;
            T x = A[S], y = A[S | (1 << i)];
            A[S] += y;
            A[S | (1 << i)] -= x;
        }
        T inv = T(1) / (1 << n);
        REP (S, 1 << n)
            A[S] *= inv;
    }
    template <typename T>
    static std::vector<T> convolution(std::vector<T> A, std::vector<T> B) {
        zeta(A);
        zeta(B);
        REP (S, A.size())
            A[S] *= B[S];
        mobius(A);
        return A;
    }
};
#undef REP_
#undef RREP_