This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ebi-fly13/Library
#include "set_function/ranked_subset_transform.hpp"
重み付きゼータ変換 / メビウス変換を行う。 $O(N^2\log N)$
#pragma once #include <array> #include <bit> #include <cassert> #include <vector> namespace ebi { template <class T, int LIM = 20> std::vector<std::array<T, LIM + 1>> ranked_zeta(const std::vector<T> &f) { int n = std::bit_width(f.size()) - 1; assert(n <= LIM); assert((int)f.size() == (1 << n)); std::vector<std::array<T, LIM + 1>> rf(1 << n); for (int s = 0; s < (1 << n); s++) rf[s][std::popcount((unsigned int)(s))] = f[s]; for (int i = 0; i < n; i++) { int w = 1 << i; for (int p = 0; p < (1 << n); p += 2 * w) { for (int s = p; s < p + w; s++) { int t = s | (1 << i); for (int d = 0; d <= n; d++) rf[t][d] += rf[s][d]; } } } return rf; } template <class T, int LIM = 20> std::vector<T> ranked_mobius(std::vector<std::array<T, LIM + 1>> rf) { int n = std::bit_width(rf.size()) - 1; assert((int)rf.size() == (1 << n)); for (int i = 0; i < n; i++) { int w = 1 << i; for (int p = 0; p < (1 << n); p += 2 * w) { for (int s = p; s < p + w; s++) { int t = s | (1 << i); for (int d = 0; d <= n; d++) rf[t][d] -= rf[s][d]; } } } std::vector<T> f(1 << n); for (int s = 0; s < (1 << n); s++) { f[s] = rf[s][std::popcount((unsigned int)(s))]; } return f; } } // namespace ebi
#line 2 "set_function/ranked_subset_transform.hpp" #include <array> #include <bit> #include <cassert> #include <vector> namespace ebi { template <class T, int LIM = 20> std::vector<std::array<T, LIM + 1>> ranked_zeta(const std::vector<T> &f) { int n = std::bit_width(f.size()) - 1; assert(n <= LIM); assert((int)f.size() == (1 << n)); std::vector<std::array<T, LIM + 1>> rf(1 << n); for (int s = 0; s < (1 << n); s++) rf[s][std::popcount((unsigned int)(s))] = f[s]; for (int i = 0; i < n; i++) { int w = 1 << i; for (int p = 0; p < (1 << n); p += 2 * w) { for (int s = p; s < p + w; s++) { int t = s | (1 << i); for (int d = 0; d <= n; d++) rf[t][d] += rf[s][d]; } } } return rf; } template <class T, int LIM = 20> std::vector<T> ranked_mobius(std::vector<std::array<T, LIM + 1>> rf) { int n = std::bit_width(rf.size()) - 1; assert((int)rf.size() == (1 << n)); for (int i = 0; i < n; i++) { int w = 1 << i; for (int p = 0; p < (1 << n); p += 2 * w) { for (int s = p; s < p + w; s++) { int t = s | (1 << i); for (int d = 0; d <= n; d++) rf[t][d] -= rf[s][d]; } } } std::vector<T> f(1 << n); for (int s = 0; s < (1 << n); s++) { f[s] = rf[s][std::popcount((unsigned int)(s))]; } return f; } } // namespace ebi