library/bitwise/Or.hpp

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

Depends on

Code

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

#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/Or.hpp"
#define REP_(i, n) for (int i = 0; i < (n); i++)
struct BitwiseOr {
    template <typename T> static void zeta(std::vector<T> &A) {
        int n = bitwise::log2(A.size());
        REP_(k, n)
        REP_(S, 1 << n) if (bitwise::in(S, k)) A[S] += A[S ^ (1 << k)];
    }
    template <typename T> static void mobius(std::vector<T> &A) {
        int n = bitwise::log2(A.size());
        REP_(k, n)
        REP_(S, 1 << n) if (bitwise::in(S, k)) A[S] -= A[S ^ (1 << k)];
    }
    template <typename T>
    static std::vector<T> convolution(std::vector<T> A, std::vector<T> B) {
        assert(A.size() == B.size());
        zeta(A);
        zeta(B);
        REP_(i, A.size()) A[i] *= B[i];
        mobius(A);
        return A;
    }
};
#undef REP_