線形代数の知識のみで理解できるhashを使った解法を紹介します。

以下常体

この問題を解くには、次の性質を満たすhashが存在すれば良い

• 部分列のhashを高速に計算できる
• 要素ごとにxor した数列のhashを高速に計算できる
• hashの衝突率が十分低い

これらを満たすハッシュを具体的に構成する。

\(2^{64}\) 未満の非負整数を \(\mathbb{F}_2\) の \(64\) 次元ベクトルとみなすことで、以下全て \(\mathbb{F}_2\) で考えているものとする（すなわち、\(+\) と書いたとき、それはxorを意味する）

最初に、\(\mathrm{GL}(64,\mathbb{F}_2)\) の元（すなわち、64×64 の正則行列）をランダムにたくさん用意し、\(M_0,M_1,\ldots,\) とする。（\(\mathbb{F}_2\) の 64×64 行列をランダムに生成したとき、それが正則である確率は \(29\%\) 程度であるため、実装上は「正則でなければ再生成」を繰り返すことで十分高速に行える）

\(F:\mathbb{Z}_{\geq 0}\to\mathrm{GL}(64,\mathbb{F}_2)\) を次のように再帰的に定める。

\(F(0)=\mathrm{id}\),
\(F(n+2^k)=M_kF(n)\) (\(n <2^k\) のとき)

この \(F\) を用いて、\(\mathbb{F}_2^{64}\) の列 \(A\) に対して \(\mathrm{hash}(A)=\sum_i F(i)A_i\) と定める。

このhash に対して、以下が成り立つ：

• 長さの等しい \(2\) つの数列に対して、衝突率は \(2^{-64}\) である。
  • \(F(i)\) が正則であることより、\(\mathrm{hash}\) の値は一様に分布するため。
• 和を保つ。すなわち、\(2\) つの数列 \(A,B\) の要素ごとの和を \(A+B\) と表すとき、\(\mathrm{hash}(A+B)=\mathrm{hash}(A)+\mathrm{hash}(B)\) を満たす。
• 数列 \(A\) の長さを \(N\) としたとき、\(O(N\log N)\) 回の行列とベクトルの積の計算を前計算として、\(A\) の任意の部分列に対する hash を \(O(\log N)\) 回の行列とベクトルの積の計算で求めることができる
  • ダブリングによる。\(\mathbb{dp}[k][i]=\mathrm{hash}((A_i,A_{i+1},\ldots,A_{i+2^k-1}))\) として、\(\mathrm{dp}[k+1][i]=\mathrm{dp}[k][i]+M_k \mathrm{dp}[k][i+2^k]\) により求める。

以上によりこのhashが望む性質を持つことがわかった。

実際には、hashにより2つの数列のcommon prefixを二分探索するためには、(任意の長さの部分列ではなく)長さ2ベキの部分列のhashがわかっていれば十分であることから、いくらか計算を省略することができ、元の問題のクエリ \(1\) つあたりは、\(O(\log N)\) 回のベクトル和で行える。

行列とベクトルの積は \(O(\log A)\) 回のbit演算で行えることから、全体の計算量は \(O(N\log N \log A+Q\log N)\) となる。なお、\(\mathbb{F}_2^{64}\) を16要素ずつ程度に分けることで、行列積を表引きできるようにして高速化することもできる（詳細略）

実装例(C++,2200ms)

（衝突率以外の \(2\) つの性質は \(M_k\) が正則でなくとも成り立ちます。\(M_k\) を正則に限らないランダム行列とした場合の衝突率がわかる方はご教示ください）

ここまで書いて気づいたんですが、\(M_i=M_0^{2^i}\) と取るとただの \(\mathbb{F}_2^{64}\) のローリングハッシュでした。

実装例(C++)