This documentation is automatically generated by online-judge-tools/verification-helper
#include "math/zeta_mobius_transform.hpp"
superset_zeta(f)
: f
を $g(S) = \displaystyle \sum_{S\subset T}f(T)$ となる g
に置き換える。superset_mobius(f)
: f
を $f(S) = \displaystyle \sum_{S \subset T}g(T)$ となる g
に置き換える。subset_zeta(f)
: f
を $g(S) = \displaystyle \sum_{S \supset T}f(T)$ となる g
に置き換える。subset_mobius(f)
: f
を $f(S) = \displaystyle \sum_{S \supset T}g(T)$ となる g
に置き換える。#pragma once
#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 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];
}
}
}
}