差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン次のリビジョン両方とも次のリビジョン | ||
| programming_algorithm:dynamic_programming:subset_convolution [2020/02/13] – [定義] ikatakos | programming_algorithm:dynamic_programming:subset_convolution [2020/02/14] – ikatakos | ||
|---|---|---|---|
| 行 19: | 行 19: | ||
| 部分集合 | 部分集合 | ||
| - | * それぞれの部分集合につき、何らかのスコアが決まっている | + | * それぞれの部分集合 |
| - | * ある部分集合 $S$ について、$S \subseteq T$ となるような全ての $T$ のスコアの総和を求めたい | + | * ある部分集合 $S_i$ について、$S_i \subseteq T$ となるような全ての $f(T)$ の総和を求めたい |
| 部分集合 | 部分集合 | ||
| - | | + | |
| | | ||
| - | S = {1} → T = {1}, {0, 1}, {1, 2}, {0, 1, 2} | + | Si = {1} |
| - | | + | → T = {1}, {0, 1}, {1, 2}, {0, 1, 2} |
| + | f(T)の総和 | ||
| * これを全ての部分集合について行うのが「ゼータ変換」であり、高速に行うアルゴリズムを「高速ゼータ変換」という。 | * これを全ての部分集合について行うのが「ゼータ変換」であり、高速に行うアルゴリズムを「高速ゼータ変換」という。 | ||
| 部分集合 | 部分集合 | ||
| - | | + | |
| Z変換 | Z変換 | ||
| - | * また、Z変換後から元のスコアを逆算する処理を「メビウス変換」という。 | + | * また、Z変換後から元の |
| - | | + | |
| | | ||
| Z変換 | Z変換 | ||
| 行 182: | 行 183: | ||
| それを考えると、メビウス変換は逆演算が可能でなければならない？ maxは逆演算できないので、メビウス変換は適用できないと思われる。 | それを考えると、メビウス変換は逆演算が可能でなければならない？ maxは逆演算できないので、メビウス変換は適用できないと思われる。 | ||
| - | ==== 最大公約数によるまとめ上げ ==== | + | ==== 包含以外の畳み込み ==== |
| + | |||
| + | ゼータ変換後の $f$ を $\zeta(f)$ とする。ゼータ変換①を式で表すと | ||
| + | |||
| + | * $\zeta(f)(S) = \sum_{S \subseteq T} f(T)$ | ||
| + | |||
| + | ここで $S$ はbitフラグを示す一般の数字と解釈すると、BitAND演算で示すことも出来る。 | ||
| + | |||
| + | * $\zeta(f)(i) | ||
| + | |||
| + | このBitAND演算を変えて畳み込みを行うバリエーションも存在する。特にゼータ変換②は、BitORにしたものである。 | ||
| - | * [[http:// | + | |
| + | * $\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_{\lcm(i, | ||
| + | * $i$ の約数であるような $j$ | ||
| + | | ||
