This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub maspypy/library
#include "setfunc/xor_convolution.hpp"
#include "setfunc/hadamard.hpp" template <typename T> vc<T> xor_convolution(vc<T> A, vc<T> B) { hadamard(A); hadamard(B); FOR(i, len(A)) A[i] *= B[i]; hadamard(A); T c = T(1) / T(len(A)); if (c != T(0)) { FOR(i, len(A)) A[i] *= c; } else { FOR(i, len(A)) A[i] /= len(A); } return A; }
#line 2 "setfunc/hadamard.hpp" // B[j] = sum_i (-1)^{popcnt(i&j)A[i]} // 2^n で割ることはしていない template <typename T> void hadamard(vc<T>& A) { int log = topbit(len(A)); assert(1 << log == len(A)); FOR(n, log) FOR(s, 1 << log) { int t = s ^ (1 << n); if (s < t) tie(A[s], A[t]) = mp(A[s] + A[t], A[s] - A[t]); } } #line 2 "setfunc/xor_convolution.hpp" template <typename T> vc<T> xor_convolution(vc<T> A, vc<T> B) { hadamard(A); hadamard(B); FOR(i, len(A)) A[i] *= B[i]; hadamard(A); T c = T(1) / T(len(A)); if (c != T(0)) { FOR(i, len(A)) A[i] *= c; } else { FOR(i, len(A)) A[i] /= len(A); } return A; }