AtCoder頻出?貼るだけ高速ゼータ・メビウス変換&約数拡張

定義

有限集合 X, (可換な)半群 G について, 写像 f:2^ X\rightarrow G , g:2^ X\rightarrow Gg(S) = \sum_{S \subseteq T} f(T) を満たすときを考える.

(※ g(S) = \sum_{T \subseteq S} f(T) の形をしたものもあるが, \bar{g}(S) := g(2^ X - S)\ , \bar{f}(T) := f(2^ X - T) と定義すれば前者と同じ形になるので割愛する.)

高速ゼータ変換

f から g を求める. O(|X|2^ {|X|})

template<typename T>
vector<T> fast_zeta_transform(const vector<T>& f) {
    int n = f.size();
    vector<T> g = f;
    for (int i = 0; (1 << i) < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (!(j >> i & 1)) {
                g[j] += g[j | (1<<i)];
            }
        }
    }
    return g;
}

例題

atcoder.jp

G := (\mathbb{N},\mathbb{N}),

 (a, b), (c, d) \in G, (a, b) + (c, d) := ((a,b,c,d) の中で一番大きな数, 二番目に大きな数)

と定義する.

f(S) := (A_S, 0)

g(S) := \max \{(A_i, A_j) | i \neq j, i, j \subseteq S \}

と定めると, g(S) = \sum_{T \subseteq S} f(T) が成立する.

包含関係が逆になってることに注意しつつ f から g を求めて, あとは S を1ずつ増やしながら\maxを更新していく.

Submission #11912671 - AtCoder Regular Contest 100

高速メビウス変換

G に逆元があるとき, g から f を求める. O(|X|2^ {|X|})

template<typename T>
vector<T> fast_mobius_transform(const vector<T>& g) {
    int n = g.size();
    vector<T> f = g;
    for (int i = 0; (1 << i) < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (!(j >> i & 1)) {
                f[j] -= f[j | (1<<i)];
            }
        }
    }
    return f;
}

約数に拡張した高速メビウス変換

自然数の集合 M = \{1, 2, \ldots, N\} , (可換な)半群 G について, 写像 f:M \rightarrow G , g:M \rightarrow Gg(d) = \sum_{d | n, n \leq N} f(n) を満たすとき, g から f を求める. O(N\log\log N)

template<typename T>
vector<T> fast_mobius_transform_prime(const vector<T>& g) {
    int n = g.size();
    vector<T> f = g;
    vector<bool> sieve(n, true);
    for (int p = 2; p < n; ++p) {
        if (!sieve[p]) continue;
        for (int i = 1; i * p < n; ++i) {
            sieve[i * p] = false;
            f[i] -= f[i * p];
        }
    }
    return f;
}

例題

atcoder.jp

M := \{1, \ldots , K\}

f(d) := \mathrm{gcd}(A_1, \ldots, A_N)d になる数列の総数

g(d) := \mathrm{gcd}(A_1, \ldots, A_N)d の倍数になる数列の総数

とおくと g(d) = \sum_{d | n, n \leq K} f(n) が成立する. g(d) = \left(\left\lfloor\frac{K}{d}\right\rfloor\right)^ N から f(d) を求めて, \sum_d f(d) \cdot d を計算する.

Submission #11899603 - AtCoder Beginner Contest 162

atcoder.jp

M := \{1, \ldots , \max(A)\}

f(d) := \mathrm{gcd}(A_i, A_j)d になる組の総数

g(d) := \mathrm{gcd}(A_i, A_j)d の倍数になる組の総数

とおくと g(d) = \sum_{d | n, n \leq \max(A)} f(n) が成立する.

C(a) := A_1, \ldots, A_N における a の出現数

を計算しておく.

A_1, \ldots, A_N の中で d の倍数であるものを B_1, \ldots, B_k とおくと


g(d) = \sum_{i < j} B_i B_j = \frac{1}{2} \left\{ \left( \sum_{l=1}^{k}B_l \right)^ 2 - \sum_{l=1}^{k}B_l ^ 2 \right\}

であり, C を用いることで g(d)O(\max(A)\log(\max(A))) で計算できる.

あとは g(d) から f(d) を求めて, \sum_d \frac{f(d)}{d} を計算する.

Submission #11899671 - AtCoder Grand Contest 038

参考

ARC100-E 「Or Plus Max」 (700) 高速ゼータ変換解法 - Mister雑記

高速ゼータ・メビウス変換 - Mister雑記

高速ゼータ変換の約数版 - noshi91のメモ

ゼータ変換・メビウス変換を理解する - Qiita