差分
このページの2つのバージョン間の差分を表示します。
両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン | ||
programming_algorithm:dynamic_programming:subset_convolution [2020/02/14] – ikatakos | programming_algorithm:dynamic_programming:subset_convolution [2020/02/14] (現在) – [高速ゼータ変換 高速メビウス変換] ikatakos | ||
---|---|---|---|
行 6: | 行 6: | ||
* [[https:// | * [[https:// | ||
- | 競プロでたまに出てくるアルゴリズムで、ちょっと直感的な理解が難しい故か、解説記事がいろいろ書かれている。 | + | 競プロでたまに出てくるアルゴリズムで、ちょっと直感的な理解が難しい故か、解説記事がいろいろ書かれている。 |
- | 更にそれを整理したキュレーション記事も既にあるため、今更独自に書く意味があるのか不明だが、まぁそこは気にせず自分用メモとして書いておく。 | + | 更にそれを整理したキュレーション記事も既にあるため、今更独自に書く意味があるか微妙だが、まぁそこは気にせず自分用メモとして書いておく。 |
===== 定義 ===== | ===== 定義 ===== | ||
行 203: | 行 203: | ||
* $\zeta(f)(i) = \sum_{\gcd(i, | * $\zeta(f)(i) = \sum_{\gcd(i, | ||
* $i$ の倍数であるような $j$ | * $i$ の倍数であるような $j$ | ||
- | * $\zeta(f)(i) = \sum_{\lcm(i, | + | * $\zeta(f)(i) = \sum_{{\rm lcm}(i,j)=i} f(j)$ |
* $i$ の約数であるような $j$ | * $i$ の約数であるような $j$ | ||
* [[http:// | * [[http:// | ||