nimber を使わない有限体の構成などについて触れています。nimber より一般的かつ、おそらく理解・実装とも簡単です。

その他の部分はだいたい公式解説と同じ方法だと思います。

---

Rolling Hash

\(K\) を環とします（環とは）。 以下簡単のため、\(K\) の加法・乗法の計算量を \(O(1)\) とします。

\(x\in K\) をランダムにとり固定します。\(K\) の元の列 \(A = (A_0, \ldots, A_n)\) に対して、ハッシュ \(H_x(A) = \sum_{i=0}^n A_ix^{n-i}\) を Rolling Hash といいます。

このハッシュは、長さ \(N\) の列に対して \(O(N)\) 時間の前計算を行うことで、任意の連続部分列のハッシュを \(O(1)\) 時間で計算できる点が優れています。

---

加法性

列 \(A = (A_0, \ldots, A_n)\) および \(B = (B_0, \ldots, B_n)\) に対して \(A+B := (A_0+B_0,\ldots,A_n+B_n)\) と定めるとき、\(H_x(A+B) = H_x(A)+H_x(B)\) が成り立ちます。証明は容易です。

---

衝突確率

\(K\) がさらに体である場合には、次が成り立ちます。

相異なる 列 \(A = (A_0, \ldots, A_n)\) および \(B = (B_0, \ldots, B_m)\) に対して、\(H_x(A)=H_x(B)\) が成り立つような \(x\) は高々 \(\max(n,m)\) 個である。したがって、\(x\in K\) をランダムにとってハッシュ関数 \(H_x\) を設計するとき、\(H_x(A) = H_x(B)\) となる確率は \(\max(n,m)/|K|\) 以下である。

証明は、因数定理より体において \(d\) 次方程式が \(d\) 個以下しか解を持たないことから分かります。 関連：Schwartz–Zippel lemma

---

本問の解法

\(K\) を、次を満たす体とします。

• \(0, 1, \ldots, 10^{18} \in K\)
• 加法が排他的論理和 \(\oplus\) と一致する

この体 \(K\) とランダムな \(x\in K\) からハッシュ関数 \(H_x\) を構成することにより、\(A[a:b] \oplus A[c:d]\) と \(A[e:f]\) の LCP の計算、辞書順比較ができます。

体 \(K\) の演算の時間計算量を \(M\) とするとき、問題全体の計算量は \(O(M(N+ Q\log N))\) となります。

---

体 \(K\) の構成

加法が \(\oplus\) と一致するような体の構成は、いくつかの方法があります。公式解説で扱われている nimber はその選択肢のひとつです。が、個人的には体の構成という目的に限れば、nimber は過剰に難解であるように思います。

ここでは次の構成方法を紹介します。

• \(\mathbb{Z}/2\mathbb{Z}\) を\(\mathbb{F}_2\) と書く。
• 多項式環 \(\mathbb{F}_2[x]\) を考え、\(d\) 次既約多項式 \(f \in \mathbb{F}_2[x]\) をとる。
• \(K = \mathbb{F}_2[x] / (f)\) とする。これは \(2^d\) 元からなる体である。

非負整数 \(\sum_{0\leq i<d} a_i2^i\) （\(a_i\in \{0,1\}\)）を \(\sum_{0\leq i<d} a_ix^i \in K\) に対応させることで、\(K = \{0,1,\ldots,2^d-1\}\) として扱うこともできて、この場合 \(K\) の加法は \(\oplus\) と一致します。

この構成において唯一自然に行えない操作は「既約多項式 \(f\) をとる」部分です。ここでは省略しますが、任意の \(d\) に対して \(d\) 次既約多項式 \(f\) は存在します。\(f\) の選択肢はたくさんあり、実はどの \(f\) をとっても得られる体は同型です。実装のためには適当な数表を参照すればよくて、例えば Conway Polynomial のテーブル

http://www.math.rwth-aachen.de/~Frank.Luebeck/data/ConwayPol/CP2.html

が参照できます。\(K\) での乗算を行うには \(\mathbb{F}_2[x]\) の乗算および \(f\) での剰余ができればよく、（おそらく nimber よりもかなり）簡単です。\(O(d)\) 回のビット演算でできる他、適当な lookup table を用意することによる高速化も可能です。

---

参考：有限体

任意の素数 \(p\) および \(d>0\) に対して、\(p^d\) 元からなる体が存在し、それらはすべて \(\mathbb{F}_p[x] / (f)\) の形で構成できます。さらに \(p^d\) 元体同士はすべて同型であることも知られています。