Math/FastMoebiusTransform.cpp

Back to top page

• category: Math
• View this file on GitHub
  • Last commit date: 2020-05-14 15:16:26+09:00

Description

(集合,値) の組 a に対して高速メビウス変換を行う。
up = true のとき : 現在の値を上位集合との和とみなし、その集合の値を取り出す。
up = false のとき : 現在の値を下位集合との和とみなし、その集合の値を取り出す。

Code

//@docs Docs/FastMoebiusTransform.md
template <class T>
void fmt(vector<T> &a, bool up) {
    int n = a.size();
    for (int i = 1; i < n; i <<= 1) {
        for (int j = 0; j < n; j++) {
            if ((j & i) == 0) {
                if (up) {
                    a[j] -= a[j | i];
                } else {
                    a[j | i] -= a[j];
                }
            }
        }
    }
}

#line 1 "Math/FastMoebiusTransform.cpp"
//@docs Docs/FastMoebiusTransform.md
template <class T>
void fmt(vector<T> &a, bool up) {
    int n = a.size();
    for (int i = 1; i < n; i <<= 1) {
        for (int j = 0; j < n; j++) {
            if ((j & i) == 0) {
                if (up) {
                    a[j] -= a[j | i];
                } else {
                    a[j | i] -= a[j];
                }
            }
        }
    }
}

Back to top page