Math/FastZetaTransform.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/FastZetaTransform.md
template <class T>
void fzt(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/FastZetaTransform.cpp"
//@docs Docs/FastZetaTransform.md
template <class T>
void fzt(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