This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub gyouzasushi/library
#include "math/bitwise_and_convolution.hpp"
bitwise_and_convolution(a, b)
c
#pragma once #include "zeta_mobius_transform.hpp" template <typename mint> std::vector<mint> bitwise_and_convolution(std::vector<mint> a, std::vector<mint> b) { superset_zeta(a); superset_zeta(b); for (int i = 0; i < int(a.size()); i++) { a[i] *= b[i]; } superset_mobius(a); return a; }
#line 2 "math/zeta_mobius_transform.hpp" #include <cassert> #include <vector> template <typename mint> void superset_zeta(std::vector<mint>& f) { int n = f.size(); assert((n & -n) == n); for (int i = 1; i < n; i <<= 1) { for (int j = 0; j < n; j++) { if ((j & i) == 0) { f[j] += f[j | i]; } } } } template <typename mint> void superset_mobius(std::vector<mint>& f) { int n = f.size(); assert((n & -n) == n); for (int i = 1; i < n; i <<= 1) { for (int j = 0; j < n; j++) { if ((j & i) == 0) { f[j] -= f[j | i]; } } } } template <typename mint> void subset_zeta(std::vector<mint>& f) { int n = f.size(); assert((n & -n) == n); for (int i = 1; i < n; i <<= 1) { for (int j = 0; j < n; j++) { if ((j & i) == 0) { f[j | i] += f[j]; } } } } template <typename mint> void subset_mobius(std::vector<mint>& f) { int n = f.size(); assert((n & -n) == n); for (int i = 1; i < n; i <<= 1) { for (int j = 0; j < n; j++) { if ((j & i) == 0) { f[j | i] -= f[j]; } } } } #line 3 "math/bitwise_and_convolution.hpp" template <typename mint> std::vector<mint> bitwise_and_convolution(std::vector<mint> a, std::vector<mint> b) { superset_zeta(a); superset_zeta(b); for (int i = 0; i < int(a.size()); i++) { a[i] *= b[i]; } superset_mobius(a); return a; }