累積和でOR/AND畳み込みをしよう
競プロで累積和を求めるアルゴリズムと、そこからある種の畳み込み操作について。
(わかりやすさ・理解のアウトプット優先で厳密性をかなり欠いています。間違い等あればTwitterか何かでお知らせください。)
累積和と差分
1次元の場合
皆さんご存じだと思います。
[1, 2, 3, 4, 5]のような配列があるとき、前から順に見て、見ている項にその前の項を足すという操作をすることで
[1, 3, 6, 10, 15]という配列が得られます。元の配列の先頭からその項までの和が各項の値になっています。
さらに、これを後ろから見て前の項を引くことで
[1, 2, 3, 4, 5]差分をとって元の配列に戻すことができます。
数式だと
のように表せます。
2次元の場合
次元でも同じことができます。行ごとに前述の(次元)累積和をとってから列ごとに累積和をとることで、各項を含めた左上部分の和を得ることができます。
[[1,2,3],↓ 行ごとに
[4,5,6],
[7,8,9]]
[[1, 3, 6]↓ 列ごとに
[4, 9,15],
[7,15,24]]
[[ 1, 3, 6]これも、行ごとに逆順に見て引き、列ごとに逆順に見て引くことで元に戻せます。
[ 5,12,21],
[12,27,45]]
数式だと
と表せます。
N次元の場合
次元のときと同じように各次元ずつ累積和をとることで、各項より添字が等しいか小さい項の和を得ることができます。(Yatesのアルゴリズム)
次元の場合でも、同じように各成分ごとに逆順に見て引くことで元に戻せます。
これは数式だと、
あるいは
と表せます。
max畳み込み
1次元の場合
これがどう畳み込みに関係してくるのでしょうか?
1次元を例にとって、累積和同士の成分ごとの積について見てみましょう。1次元の配列の累積和をそれぞれとします。
これを、1次元の累積和とみなして元の配列に戻す操作をすると、項目は
と表すことができます。これはすなわち、添字がいずれも以下の項のうちいずれも以下の項を引いている、つまりのいずれかがの項が残ることとなります。すなわち、
ということです。
つまり、「2つの配列の累積和をとって、各項をかけて差分をとって元に戻す」ことで、添字の最大値について畳み込みができました!以下、これをmax畳み込みと呼ぶことにしましょう。
N次元max畳み込み
では次元ではどうでしょうか?少しややこしいですが、次元の場合と変わりません。次元の配列の累積和をそれぞれとします。
見慣れない書き方だと思いますが、先ほどのを個連ねた形と同じです。この差分は、1次元のときと同様に成分で増えた項を考えると、
となり、次元配列でも無事max畳み込みができていると思います。
集合をbitsetで表そう
競プロerの皆さんはもうご存じと思いますが、有限集合の部分集合は、ビット演算によって表現することができます。
例えば、としたとき、この部分集合は進表記でというふうに、の元と整数の進表記の各桁を対応させることができます。
bitsetでの累積和
部分集合が進表記で表せることを別の視点から見ましょう。この進表記 (bitset) を添字とする配列、すなわちの次元配列を考えたらどうなるでしょうか?これでmax畳み込みをしたら?
高速ゼータ変換・メビウス変換
まず、添字がbitsetの累積和が一体何なのか考えてみます。
これを集合の書き方で表すと、
だいぶすっきりしました。付け加えると、この累積和・差分の操作は「下位集合に対するゼータ/メビウス変換」と呼ばれることもあります。
累積和・差分をとる向きを逆にすると、の添字の方向が逆になって
すなわち
となります。先ほど同様に、この逆順の累積和・差分の操作は、「上位集合に対するゼータ/メビウス変換」と呼ばれることもあります。
これらの操作を定義通りにやると、通りの部分集合に対して通りの部分集合がありえるため、計算量がとなってしまいます。しかし、累積和・各項乗算・差分をする先ほどの方法だとで済ませることができます。
OR畳み込み
とりうる値が2通りしかない場合は、真理値表が有効です。でのが持つ意味を考えてみると、
i | j | max{i,j} |
---|---|---|
0 | 0 | 0 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 1 |
これは論理和に他なりません!
すなわち、先ほどのmax畳み込みをこの次元配列で行うと、成分ごとのはビットごとのORとなり、すなわち集合で考えれば和集合なので、
となり、累積和でゼータ変換を行い*1、各項かけて差分をとる*2ことで、添字の和集合に対する畳み込みがでできることが分かりました。
AND畳み込み
添字の積集合に対する畳み込みも同様にできます。累積和・差分を取る向きを逆にすると、添字のmin (bitsetではAND) で畳み込みをすることになります。一応真理値表を見ると、
i | j | min{i,j} |
---|---|---|
0 | 0 | 0 |
0 | 1 | 0 |
1 | 0 | 0 |
1 | 1 | 1 |
となっており、確かに桁毎のminとビット毎のANDが対応することが分かります。
まとめ
bitDPで、
- 各bitを添字とした次元配列として累積和をとると、ゼータ変換ができる。
- 各bitを添字とした次元配列として差分をとると、メビウス変換ができる。
- 定義から愚直にやるとかかるこれら操作が、累積和でになる。
- さらに、累積和・各項乗算・差分の操作によって添字のOR/ANDに対する畳み込み操作がでできる。
and more
その他にも、整数の素因数分解表示を配列の添字とすることにより、min/max畳み込みをすることで添字のLCM/GCDに対する畳み込み操作が線形対数時間でできる、というテクニックがあります (むしろこちらの方が有名かもしれない)。
また、各種の畳み込み操作の計算量を愚直から変換・各項乗算・逆変換に落とす方法はいくつか知られています。