AtCoder頻出?貼るだけ高速ゼータ・メビウス変換&約数拡張
定義
有限集合 , (可換な)半群 について, 写像 , が を満たすときを考える.
(※ の形をしたものもあるが, と定義すれば前者と同じ形になるので割愛する.)
高速ゼータ変換
から を求める.
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; }
例題
の中で一番大きな数, 二番目に大きな数
と定義する.
と定めると, が成立する.
包含関係が逆になってることに注意しつつ から を求めて, あとは を1ずつ増やしながらを更新していく.
Submission #11912671 - AtCoder Regular Contest 100
高速メビウス変換
に逆元があるとき, から を求める.
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; }
約数に拡張した高速メビウス変換
自然数の集合 , (可換な)半群 について, 写像 , が を満たすとき, から を求める.
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; }
例題
が になる数列の総数
が の倍数になる数列の総数
とおくと が成立する. から を求めて, を計算する.
Submission #11899603 - AtCoder Beginner Contest 162
が になる組の総数
が の倍数になる組の総数
とおくと が成立する.
における の出現数
を計算しておく.
の中で の倍数であるものを とおくと
であり, を用いることで を で計算できる.
あとは から を求めて, を計算する.
Submission #11899671 - AtCoder Grand Contest 038