差分
このページの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:// | ||
- | 競プロでたまに出てくるアルゴリズムで、ちょっと直感的な理解が難しい故か、解説記事がいろいろ書かれている。 | + | 競プロでたまに出てくるアルゴリズムで、ちょっと直感的な理解が難しい故か、解説記事がいろいろ書かれている。 |
- | 更にそれを整理したキュレーション記事も既にあるため、今更独自に書く意味があるのか不明だが、まぁそこは気にせず自分用メモとして書いておく。 | + | 更にそれを整理したキュレーション記事も既にあるため、今更独自に書く意味があるか微妙だが、まぁそこは気にせず自分用メモとして書いておく。 |
===== 定義 ===== | ===== 定義 ===== | ||
行 183: | 行 183: | ||
それを考えると、メビウス変換は逆演算が可能でなければならない? maxは逆演算できないので、メビウス変換は適用できないと思われる。 | それを考えると、メビウス変換は逆演算が可能でなければならない? maxは逆演算できないので、メビウス変換は適用できないと思われる。 | ||
- | ==== 最大公約数によるまとめ上げ | + | ==== 包含以外の畳み込み |
- | | + | ゼータ変換後の f を ζ(f) とする。ゼータ変換①を式で表すと |
+ | |||
+ | * ζ(f)(S)=∑S⊆Tf(T) | ||
+ | |||
+ | ここで S はbitフラグを示す一般の数字と解釈すると、BitAND演算で示すことも出来る。 | ||
+ | |||
+ | * ζ(f)(i)=∑i AND j=if(j) | ||
+ | |||
+ | このBitAND演算を変えて畳み込みを行うバリエーションも存在する。特にゼータ変換②は、BitORにしたものである。 | ||
+ | |||
+ | * ゼータ変換② | ||
+ | * ζ(f)(i)=∑i OR j=if(j) | ||
+ | * maxによる畳み込み | ||
+ | * ζ(f)(i)=∑max(i,j)=if(j) | ||
+ | * 単なる累積和っぽい? | ||
+ | * 最大公約数、最小公倍数による畳み込み | ||
+ | * ζ(f)(i)=∑gcd(i,j)=if(j) | ||
+ | * i の倍数であるような j | ||
+ | * ζ(f)(i)=∑lcm(i,j)=if(j) | ||
+ | * i の約数であるような j | ||
+ | | ||