E - XOR Matching 解説
by 
maspy
XOR 畳み込み解法の高速化
次の解説の特に [3] の部分を前提とします．
本問は基本的には上の解説のように，複数の計算方法を使い分けることが想定されています．しかし，ひとつの解法をしっかりと定数倍高速化することでも正答を得られます．ここではそのことを紹介します．
[1] 概要
\(C\) の種類数を \(K\) として，解法は次の形に整理できます．
- 長さ \(2^M\) の列を \(K\) 個作る．\(S_1, S_2, \ldots, S_K\) とする．
- それぞれの \(S_j\) について，\(\mathrm{ANS}\) に \(\mathrm{conv}(S_j,S_j)\) の適当な定数倍を加える（ただし \(\mathrm{conv}\) は XOR 畳み込みとする）．
この解法をアルゴリズムの工夫により高速化して，正答を得ることが目標です．
[2] 単純な実装での Hadamard 変換の回数
\(\mathrm{conv(A,B)}\) は Hadamard 変換により \(O(M2^M)\) 時間で計算できます．具体的には次の手順です．
HA := hadamard_transform(A)
HB := hadamard_transform(B)
HC := pointwise product of HA and HB (HC[i]=HA[i]*HB[i])
conv_AB := hadamard_transform(HC) / 2^M
計算は \(3\) 回の Hadamard 変換を含み，全体では \(3K\) 回の Hadamard 変換が必要です．
[3] Hadamard 変換回数の節約 (1)
本問で必要なのは \(\mathrm{conv}(S,S)\) つまり \(A=B\) の場合です．したがって，まず同じ列の Hadamard 変換を反復する無駄を節約することで，\(\mathrm{conv}(S,S)\) に必要な Hadamard 変換を \(2\) 回に減らすことができます．
for S in [S1, S2, ..., SK]:
HS := hadamard_transform(S)
HT := pointwise square of HS
ANS += (some coefficient) * hadamard_transform(HT) / 2^M
全体では \(2K\) 回の Hadamard 変換が必要です．
[4] Hadamard 変換回数の節約 (2)
さらに，ANS が \(K\) 個の hadamard 変換を足し合わせたものになっていることが非効率で，これらを次のようにまとめることができます．
for S in [S1, S2, ..., SK]:
HS := hadamard_transform(S)
HT := pointwise square of HS
tmp += (some coefficient) * HT
ANS := hadamard_transform(tmp) / 2^M
このような方法をとれば，必要な Hadamard 変換の回数は \(K+1\) 回で済みます．単純に XOR convolution(A,B) を反復する方法に比べて，\(3\) 倍程度の高速化が期待できます．
本問題の実行時間制限は，このような定数倍高速化を行った上で，Library Checker での実行時間が最速である実装に近い実装を行った場合に，コンテスト開催時点での実行環境で，AC と TLE の境界付近となる程度に設定されています．
[5] Hadamard 変換回数の節約 (3)
複数の Hadamard 変換をひとつの整数型で並列して行うことで，さらに数倍の高速化が期待できます．例えば，絶対値が \(2^{19}\) 未満の整数の \(3\) つ組 \((a,b,c)\) をひとつの整数 \((a+2^{20}b+2^{40}c)\) に対応させて扱えば，さらに Hadamard 変換の回数を \(1/3\) 倍程度に抑えることもできます（ただし負の整数の扱いに慎重な実装が必要です）．
投稿日時:
最終更新: