倍数についてのゼータ変換/メビウス変換
(convolution/multiple-zeta-moebius-transform.hpp)
TODO: map
で渡すタイプのゼータ/メビウス変換について書く
概要
計算量は $ O(N \log \log N) $ にできるけど、よくわからないので妥協。
倍数についてのゼータ変換
vector<T> zeta_transform_naive<T, op>(const vector<T>& A)
可換な二項演算(大抵の場合、数の和) $\oplus$ があるとき、
長さ$N$の数列$A$が与えられたときに、 $ B_i = \bigoplus_{i \mid j} A_j $ なる数列 $B$ を求める。
op
は、例えばT=int
で二項演算が和なら
int op(int a, int b){
return a + b;
}
などとして定義された関数を渡す。
計算量
倍数についてのメビウス変換
可換な二項演算(大抵の場合、数の和) $\oplus$ に逆元があるとき、
長さ$N$の数列$B$が与えられたときに、$B_i = \bigoplus_{i \mid j} A_j $ なる 数列$A$ を求める。
vector<T> moebius_transform_naive<T, invop>(const vector<T>& B)
invopは、例えばT=int
で、二項演算が和なら
int invop(int a, int b) {
return a - b;
}
などとして定義された関数を渡す。
計算量
mapでやるやつ
map<I,T> zeta_transform<I,T,op>(const map<I,T>& mp)
map<I,T> moebius_transform<I,T,invop>(const map<I, T>& mp)
どちらもゼータ変換/メビウス変換を行うが、vector
で変換する場合と違い、map
のkeyだけを添え字として扱う。
メビウス関数を使うと、
$ g(n) = \bigoplus_{n \mid i} f(i) \Leftrightarrow f(n) = \bigoplus_{ n \mid i} \mu (\frac i n) g(i) $ と表せるらしい。
計算量
map
のサイズを$N$として
何が嬉しいのか
数列$A$と$B$が与えられたとして、倍数についてのゼータ変換をすることで
$ A^{\prime}$と $B^{\prime}$ を得る。 $ A^{\prime}i B^{\prime}_i = \Sigma{i \mid j , i \mid k} A_j B_k $ であり、
$ {i \mid j , i \mid k} $ とは $ i \mid gcd(j,k) $ と言い換えられるから、$A^{\prime} B^{\prime} $ を倍数についてメビウス変換することで、gcd畳み込みができる、みたいな感じ。(書いてて自信なくなってきたな。間違ってるかも)
Verified with
Code
Back to top page