ganmo::cout

競技プログラミング始めました

累積和でOR/AND畳み込みをしよう

競プロで累積和を求めるアルゴリズムと、そこからある種の畳み込み操作について。
(わかりやすさ・理解のアウトプット優先で厳密性をかなり欠いています。間違い等あればTwitterか何かでお知らせください。)

累積和と差分

1次元の場合

皆さんご存じだと思います。

[1, 2, 3, 4, 5]
のような配列があるとき、前から順に見て、見ている項にその前の項を足すという操作をすることで
[1, 3, 6, 10, 15]
という配列が得られます。元の配列の先頭からその項までの和が各項の値になっています。
さらに、これを後ろから見て前の項を引くことで
[1, 2, 3, 4, 5]
差分をとって元の配列に戻すことができます。

数式だと
\displaystyle s_i=\sum_{j=1}^i a_j
\displaystyle s_i-s_{i-1}=a_i
のように表せます。

2次元の場合

2次元でも同じことができます。行ごとに前述の(1次元)累積和をとってから列ごとに累積和をとることで、各項を含めた左上部分の和を得ることができます。

[[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]]
これも、行ごとに逆順に見て引き、列ごとに逆順に見て引くことで元に戻せます。

数式だと
\displaystyle s_{i,j} = \sum_{k=1}^i \sum_{l=1}^j a_{k,l}
と表せます。

N次元の場合

2次元のときと同じように各次元ずつ累積和をとることで、各項より添字が等しいか小さい項の和を得ることができます。(Yatesのアルゴリズム)
N次元の場合でも、同じように各成分ごとに逆順に見て引くことで元に戻せます。

これは数式だと、
\displaystyle s_{i_1,i_2,\cdots,i_N} = \sum_{j_1=1}^{i_1} \sum_{j_2=1}^{i_2} \cdots \sum_{j_N=1}^{i_N} a_{j_1,j_2,\cdots,j_N}
あるいは
\displaystyle s_{i_1,i_2,\cdots,i_N} = \sum_{j_1 \le i_1} \sum_{j_2 \le i_2} \cdots \sum_{j_N \le i_N} a_{j_1,j_2,\cdots,j_N}
と表せます。

max畳み込み

1次元の場合

これがどう畳み込みに関係してくるのでしょうか?
1次元を例にとって、累積和同士の成分ごとの積について見てみましょう。1次元の配列\{a_i\}, \{b_i\}の累積和をそれぞれ\{s_i\},\{t_i\}とします。
\displaystyle \begin{eqnarray}
s_i t_i
&=& \left( \sum_{j=1}^i a_j \right) \left( \sum_{k=1}^i b_k \right) \\
&=& \sum_{j=1}^i \sum_{k=1}^i a_j b_k.
\end{eqnarray}
これを、1次元の累積和とみなして元の配列に戻す操作をすると、i項目は
\displaystyle \begin{eqnarray}
s_i t_i - s_{i-1} t_{i-1}
&=& \sum_{j=1}^i \sum_{k=1}^i a_j b_k - \sum_{j=1}^{i-1} \sum_{k=1}^{i-1} a_j b_k
\end{eqnarray}
と表すことができます。これはすなわち、添字がいずれもi以下の項のうちいずれもi-1以下の項を引いている、つまりj, kのいずれかがiの項が残ることとなります。すなわち、
\displaystyle \begin{eqnarray}
s_i t_i - s_{i-1} t_{i-1}
&=& \sum_{\max\{j,k\}=i} a_j b_k
\end{eqnarray}
ということです。
つまり、「2つの配列の累積和をとって、各項をかけて差分をとって元に戻す」ことで、添字の最大値について畳み込みができました!以下、これをmax畳み込みと呼ぶことにしましょう。

N次元max畳み込み

ではN次元ではどうでしょうか?少しややこしいですが、1次元の場合と変わりません。N次元の配列\{a_{i_1,\cdots,i_N}\}, \{b_{i_1,\cdots,i_N}\}の累積和をそれぞれ\{s_{i_1,\cdots,i_N}\},\{t_{i_1,\cdots,i_N}\}とします。
\displaystyle \begin{eqnarray}
s_{i_1,\cdots,i_N} t_{i_1,\cdots,i_N}
&=& \left( \sum_{j_1 \le i_1, \cdots, j_N \le i_N} a_{j_1,\cdots,j_N} \right) \left( \sum_{k_1 \le i_1, \cdots, k_N \le i_N} b_{k_1,\cdots,k_N} \right) \\
&=& \sum_{j_1 \le i_1, \cdots, j_N \le i_N} \sum_{k_1 \le i_1, \cdots, k_N \le i_N} a_{j_1,\cdots,j_N} b_{k_1,\cdots,k_N}
\end{eqnarray}
見慣れない書き方だと思いますが、先ほどの\sumN個連ねた形と同じです。この差分は、1次元のときと同様に(i_1,\cdots,i_N)成分で増えた項を考えると、
\displaystyle \begin{eqnarray}
\Delta_{i_1,\cdots,i_N}
&=& \sum_{\max\{j_1,k_1\}=i_1, \cdots, \max\{j_N,k_N\}=i_N} a_{j_1, \cdots, j_N} b_{k_1, \cdots, k_N}
\end{eqnarray}
となり、N次元配列でも無事max畳み込みができていると思います。

集合をbitsetで表そう

競プロerの皆さんはもうご存じと思いますが、有限集合Aの部分集合は、ビット演算によって表現することができます。
例えば、A=\{a,b,c,d,e\}としたとき、この部分集合B=\{a,d,e\}2進表記で10011というふうに、Aの元と整数の2進表記の各桁を対応させることができます。

bitsetでの累積和

部分集合が2進表記で表せることを別の視点から見ましょう。この2進表記 (bitset) を添字とする配列、すなわち2\times2\times\cdots\times2|A|次元配列を考えたらどうなるでしょうか?これでmax畳み込みをしたら?

高速ゼータ変換・メビウス変換

まず、添字がbitsetの累積和が一体何なのか考えてみます。
\displaystyle \begin{eqnarray}
s_{i_1, \cdots, i_N}
&=& \sum_{j_1\le i_1, \cdots, j_N \le i_N} a_{j_1, \cdots, j_N}
\end{eqnarray}
これを集合の書き方で表すと、
\displaystyle \begin{eqnarray}
s_A
&=& \sum_{B \subseteq A} a_B
\end{eqnarray}
だいぶすっきりしました。付け加えると、この累積和・差分の操作は「下位集合に対するゼータ/メビウス変換」と呼ばれることもあります。

累積和・差分をとる向きを逆にすると、\sumの添字の方向が逆になって
\displaystyle \begin{eqnarray}
s_{i_1, \cdots, i_N}
&=& \sum_{j_1\ge i_1, \cdots, j_N \ge i_N} a_{j_1, \cdots, j_N}
\end{eqnarray}
すなわち
\displaystyle \begin{eqnarray}
s_A
&=& \sum_{B \supseteq A} a_B
\end{eqnarray}
となります。先ほど同様に、この逆順の累積和・差分の操作は、「上位集合に対するゼータ/メビウス変換」と呼ばれることもあります。

これらの操作を定義通りにやると、2^{|A|}通りの部分集合に対してO(2^{|A|})通りの部分集合がありえるため、計算量がO(4^{|A|})となってしまいます。しかし、累積和・各項乗算・差分をする先ほどの方法だとO(|A|2^{|A|})で済ませることができます。

OR畳み込み

とりうる値が2通りしかない場合は、真理値表が有効です。\{0,1\}での\maxが持つ意味を考えてみると、

i j max{i,j}
0 0 0
0 1 1
1 0 1
1 1 1

これは論理和に他なりません!
すなわち、先ほどのmax畳み込みをこの|A|次元配列で行うと、成分ごとの\maxはビットごとのORとなり、すなわち集合で考えれば和集合なので、
\displaystyle \Delta[s_A t_A] = \sum_{X\cup Y=A} a_X b_Y
となり、累積和でゼータ変換を行い*1、各項かけて差分をとる*2ことで、添字の和集合に対する畳み込みがO(N2^N)でできることが分かりました。

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を添字とした|A|次元配列として累積和をとると、ゼータ変換ができる。
  • 各bitを添字とした|A|次元配列として差分をとると、メビウス変換ができる。
  • 定義から愚直にやるとO(4^{|A|})かかるこれら操作が、累積和でO({|A|}2^{|A|})になる。
  • さらに、累積和・各項乗算・差分の操作によって添字のOR/ANDに対する畳み込み操作がO({|A|}2^{|A|})でできる。

and more

その他にも、整数の素因数分解表示を配列の添字とすることにより、min/max畳み込みをすることで添字のLCM/GCDに対する畳み込み操作が線形対数時間でできる、というテクニックがあります (むしろこちらの方が有名かもしれない)。

また、各種の畳み込み操作の計算量を愚直O(N^2)から変換・各項乗算・逆変換O(N\log N)に落とす方法はいくつか知られています。

などなど…
しかし、ゼータ変換・メビウス変換とこれらの変換は形は似れども分けて考えるべきもののようです*3

*1:このアルゴリズムは高速ゼータ変換(FZT)と呼ばれるらしいです。

*2:同様に高速メビウス変換(FMT)と呼ばれるらしいです。

*3:参考: maspyさんの記事 [数学] 畳み込み入門:Dirichlet積とゼータ変換・メビウス変換 | maspyのHP