Complementary Subset Transform 解説

TODO: ちゃんと書く (ごめんなさい)

概要だけ:

準備

まず、(下位集合版の) 高速ゼータ変換をオンラインでやる方法を考える。ただし、添字の小さい順に値が与えられるものとする。

このとき、高速ゼータ変換の過程において遷移をすぐに足しこむのではなく、バッファに溜めておき、必要になった段階でバッファから取り出していくようにすれば時間計算量は変わらず $\Theta(N\cdot 2^N)$ で計算できる。ただし、バッファのための空間が必要なので、空間計算量も $\Theta(N\cdot 2^N)$ となる。

(下位集合版の) 高速メビウス変換も全く同様にしてオンラインで出来る (足しこむ処理を差し引く処理に変えれば OK)。

本解法

入力を前から処理し、$t_i=0$ ならオンライン高速ゼータ変換、$t_i=1$ ならメビウス変換の処理を行う。桁を見る順番をゼータ変換とメビウス変換で逆にしてあげると、ゼータ変換用のバッファとメビウス変換用のバッファを別々に持たなくても良くなって嬉しい。

計算量は時間/空間ともに $\Theta(N \cdot 2^N)$。

実装

C++

提出リンク

Java

提出リンク

Python (PyPy)

提出リンク