AtCoder ABC 150 - こんちゅう

解けなかった問題を覚書程度に記す。
atcoder.jp

ABC150F

難しくない？？（ずっと言ってる）

結局XOR演算について正しく理解しているかという話になる。基本的な性質はググれば出てくるが，
$a\oplus b=b\oplus a$
$(a\oplus b)\oplus c=a\oplus (b\oplus c)$
$a\oplus a=0, a\oplus 0=a$
$a\oplus c = b\oplus c \Leftrightarrow a=b$
$a\oplus c \neq b\oplus c \Leftrightarrow a\neq b$
くらいだろうか。証明は真理値表より。

$a_{k}\oplus x, a_{k+1}\oplus x,\cdots ,a_{k-1}\oplus x$ と $b_0,b_1,\cdots ,b_N$ が全て一致すれば言いわけだが，もしこれがとあるkについて成立していれば，すべてのiに対して， $a_{k+i}\oplus x \oplus a_{k+i+1} \oplus x=b_i\oplus b_{i+1}$ が成立している。これは先ほど述べた性質より $a_{k+i}\oplus a_{k+i+1}$ と一致しているため，このようなkをKMP法を用いて探せばいい。逆を考えることで $x$ を特定できる。
KMP法についてはググったら出てくる。が，結構理解する&実装するのに時間がかかった。でももうライブラリも整備したし，次は大丈夫。なはず。

このままだとeditorialそのままなので何か書く。例えば $a_i=0,1$ ， $b_i=1,2$ ， $x=0,1$ であり，XORがただの足し算であるような状況を考える。
$A:0,0,1,0,0,1,0,1$
$B:2,1,1,2,1,2,1,1$
このとき，条件を満たすような $k,x$ を探すのに $O(N^2)$ かける人はいない。Aはただシフトして同じものを足しているだけなので，例えばそれらの差分は変わらない。差分を用いてBと効率的に比較できる。
ところでこの状況は一般的である。つまり，2を0と置き換え， $a_i$ をbitごとに別の数列として改めておくと，問題の状況と完全に一致する。