差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン最新のリビジョン両方とも次のリビジョン | ||
| programming_algorithm:dynamic_programming:subset_convolution [2020/02/14] – [定義] ikatakos | programming_algorithm:dynamic_programming:subset_convolution [2020/02/14] – [包含以外の畳み込み] ikatakos | ||
|---|---|---|---|
| 行 183: | 行 183: | ||
| それを考えると、メビウス変換は逆演算が可能でなければならない？ maxは逆演算できないので、メビウス変換は適用できないと思われる。 | それを考えると、メビウス変換は逆演算が可能でなければならない？ maxは逆演算できないので、メビウス変換は適用できないと思われる。 | ||
| - | ==== 最大公約数によるまとめ上げ | + | ==== 包含以外の畳み込み |
| - | | + | ゼータ変換後の $f$ を $\zeta(f)$ とする。ゼータ変換①を式で表すと |
| + | |||
| + | * $\zeta(f)(S) = \sum_{S \subseteq T} f(T)$ | ||
| + | |||
| + | ここで $S$ はbitフラグを示す一般の数字と解釈すると、BitAND演算で示すことも出来る。 | ||
| + | |||
| + | * $\zeta(f)(i) = \sum_{i \ AND \ j=i} f(j)$ | ||
| + | |||
| + | このBitAND演算を変えて畳み込みを行うバリエーションも存在する。特にゼータ変換②は、BitORにしたものである。 | ||
| + | |||
| + | * ゼータ変換② | ||
| + | * $\zeta(f)(i) = \sum_{i \ OR \ j=i} f(j)$ | ||
| + | * maxによる畳み込み | ||
| + | * $\zeta(f)(i) = \sum_{\max(i, | ||
| + | * 単なる累積和っぽい? | ||
| + | * 最大公約数、最小公倍数による畳み込み | ||
| + | * $\zeta(f)(i) = \sum_{\gcd(i, | ||
| + | * $i$ の倍数であるような $j$ | ||
| + | * $\zeta(f)(i) = \sum_{{\rm lcm}(i, | ||
| + | * $i$ の約数であるような $j$ | ||
| + | | ||
