ABC 274 Ex — XOR Sum of Arrays

考察

lexicographic comparisonは二列のLCP長を求め、最初の不一致要素またはlengthだけを比較すればよい。

通常rolling hashはelementwise additionに線形だが、nimber fieldではfield additionがbitwise XORなので H(B xor C)=H(B) xor H(C) が成り立つ。

棄却する候補: 各queryでXOR列を実際に生成し、target subarrayと先頭から比較する。

query lengthの総和がNQ規模になり得る。

採用する候補: 64-bit nimbers上のrandom-base rolling hashを前計算し、virtual XOR sequenceとtargetのprefix equalityをbinary searchしてLCPを得る。

各substring hashとXOR-combined hashを定数時間で作れ、一queryをO(log N) hash comparisonsにできる。

hash(A[a..a+k)) xor hash(A[c..c+k))がelementwise XOR列prefixのhashに一致するため、virtual sequenceをmaterializeせずequality判定できる。

LCPがmin(leftLength,rightLength)未満なら実値A_{a+l} xor A_{c+l}とA_{e+l}を比較し、全prefix一致なら短い列だけがstrictly smallerである。

XORを加法とするfinite fieldへrolling hashを移植し、linear hash compositionとLCP binary searchでvirtual arraysを比較する。

XORを加法に持つ64-bit体を構成する

Nim積は非負整数a,bに対して

a ⊗ b = mex{(a'⊗b) xor (a⊗b') xor (a'⊗b') : 0≤a'<a, 0≤b'<b}

と定義される。mexは集合にない最小非負整数。0⊗a=0、1⊗a=aになる。幅w=1,2,4,8,…bitの整数0,…,2^w−1はxorとNim積について閉じた体F_{2^w}になる。この構造の定理を用い、巨大なmex集合は実行時に作らず、次の二次拡大の再帰で積を計算する。

w=2hとし、θ=2^hを上半分の基底とする。整数a=a_0 xor (a_1<<h)をa_0+a_1θと読む。a_0,a_1はそれぞれh-bitの下位体の元であり、整数のbit列をこの基底の係数としてそのまま使う。Nim積では

θ² = θ + η,   η=2^(h−1) ∈ F_{2^h}

が成立する。ここで+はxor、整数の普通の積とは違う。最初の拡大はh=1、η=1でθ²=θ+1、つまり2⊗2=3。下位体の積ができれば、この関係を使って上位体の積も閉じた形で求められる。

この二次拡大が体を作る理由は、拡大有限体の単元のtraceによる既約性の説明を参照する。ここでは加法がxorで、以下の乗法が分配則を満たすことを使う。

半分へ再帰する乗法とtableの底

b=b_0+b_1θも分解し、下位体で

c = a_1 ⊗ b_1
d = a_0 ⊗ b_0
e = (a_0 xor a_1) ⊗ (b_0 xor b_1)
low  = d xor (c ⊗ η)
high = d xor e
result = low xor (high << h)

とする。展開すると交差項はe xor c xor dで、θ²の置換により上位係数へcが加わるためhigh=e xor d、定数へc⊗ηが加わるためlowの式になる。四つの積は全てh-bitの下位体内なのでwを半分にして再帰できる。w=1では0/1の普通の積を返す。aまたはbが0/1の場合は幅によらず0または他方を直接返してよい。

実用実装ではsmall[a][b](0≤a,b<256)を前計算する。tableを構築する時はtable参照を無効にした上の再帰をw=8からw=1まで行い、全256²組を埋める。以後の64-bit乗算ではw≤8でこのtableを参照して止める。64→32→16→8の三段、各段高々四呼出しなので最大64回のtable参照で済む。256²個の8-bit積と固定幅のbit演算という定数費用まで明示すれば、全prefixとqueryの計算量へ接続できる。

例えば3=1+θなので2⊗3=θ(1+θ)=1。また2⊗(2 xor 3)=2で、(2⊗2) xor (2⊗3)=3 xor 1=2と一致する。この分配則こそ、列の要素ごとのxorをhashのxorへ移す根拠である。

構成した体でprefix hashを作る

Nim積を⊗、加法をxorと書く。基数β、pow[0]=1、pow[t+1]=pow[t]⊗βを用い、prefix[0]=0、prefix[i+1]=(prefix[i]⊗β) xor A_iとする。0-based半開区間[l,r)のhashはprefix[r] xor (prefix[l]⊗pow[r−l])。これで全substringを同じ次数へ揃えられ、同長の二列のhashをxorするだけで要素ごとのXOR列のhashが得られる。

長さkでこの合成hashと第三列のprefix hashを比べ、共通prefix長を二分探索する。hash衝突がなければ一致判定は単調。探索後は実要素を比較し、共通prefixだけで片方が尽きた場合は長さを比較する。hashは確率的な一致判定であり、体上の線形性そのものは厳密だが、異なる列のhash一致を完全には排除しない。

典型の発動条件

rolling hashによるLCP二分探索

発動条件: 多数のsubstring/virtual sequenceをlexicographically比較し、prefix equalityを高速判定できるとき。

prefix length kのhash一致をpredicateとして最大共通prefix長をbinary searchする。

演算に線形なhash fieldの選択

発動条件: elementwise演算後のsequence hashをoperand hashesから直接合成したいとき。

XORが加法になるnimber fieldとNim productをrolling-hashの係数演算に用いる。

問題固有の要素

64-bit nimber hashでruntime-random baseを選ぶと、入力を固定するjudgeがcollision rootを狙うことを防ぎ、長さに対して小さいfailure probabilityを得る。

別の問題へ持ち帰る視点: combined sequenceの演算とhash加法を一致させるには、その演算を加法に持つalgebraic fieldを探す。

正当性

体の乗法はXORに分配するため、二つの部分列指紋のXORが仮想XOR列の指紋になる。指紋衝突がなければ、LCP探索後の実値比較は通常の辞書順比較に一致する。二次拡大の既約性と具体的な還元式は参照先単元・考察のとおりで、異なる列の誤一致確率は非零多項式の根の個数で抑えられる。

実装上の注意

  • 乗法をunsigned 64bit、下位maskを(1ULL<<h)−1で扱う。分割後h≤32なので64bit幅のshiftを行わない。ηは1ULL<<(h−1)。
  • smallはtable参照を無効にした再帰で全256²組を構築してから使う。通常整数積をNim積の代わりに使わない。
  • substring hashの次数をprefix式とpowersで統一する。基数は固定入力と独立な実行時乱数とし、0,1を除外するなら候補集合の大きさ2^64−2で衝突上界を評価する。

復習の核

  • virtual elementwise sequenceの比較は、演算に線形なhashを作ってprefix equality oracleにする。
  • lexicographic判定ではLCP探索後の不一致比較と、片方がprefixになったlength比較を分離する。

計算量と制約

時間

T=256²組の8-bit乗法tableを固定幅再帰で一度作る定数前計算と、O(N+Q log N)回の64-bit体乗法。一乗法は64→32→16→8の高々三段で最大64回のtable参照。固定bit幅を定数とすれば全体O(N+Q log N)。

空間

O(N+256²)。prefix hash、基数冪、8-bit乗法table。

制約との対応

公式制約の確認範囲: Time limit: 4 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N \leq 5 \times 10^5; 0 \leq A_i \leq 10^{18}; 1 \leq Q \leq 5 \times 10^4; 1 \leq a \leq b \leq N; 1 \leq c \leq d \leq N; 1 \leq e \leq f \leq N; b - a = d - c; All values in the input are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

XOR Sum of Arrays の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 列・文字列のrolling fingerprint

主題
  • 列・文字列のrolling fingerprint: 順序を保つprefix hashと連結則を設計し、部分列のhash差やLCP二分探索で列の一致を比較する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
追加で学ぶ技能
既習技能
    なし

    主タグ: 拡大有限体の表現と演算 列・文字列のrolling fingerprint

    執筆: abc-explanation-author1.1.1 / revision 5

    学習の位置

    体系上の位置: 列・文字列のrolling fingerprint

    • 順序を保つprefix hashと連結則を設計し、部分列のhash差やLCP二分探索で列の一致を比較する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
    • 基底と既約関係を定めて拡大有限体の元を一意に表し、標準形を保つ加減乗除を実装できる。

    学習記録

    状況更新: 更新記録なし

    復習設定更新: 更新記録なし

    端末内の保存状態を確認しています。

    要復習一覧 / 学習記録のバックアップ / 解説に戻る

    同じ単元の問題