Xor Shift [AtCoder Beginner Contest 150 F]

https://atcoder.jp/contests/abc150/tasks/abc150_f

解説

https://atcoder.jp/contests/abc150/submissions/9414606

自明な所から考えると、kを固定すると、a[i] = b[i+k] XOR xということは、
a[i] XOR b[i+k] = xなので、xは一意に定まる。
なので、kを固定すると、最初の1要素でxがわかり、他の要素にてそれが成り立つか確認できればいい。

操作をまとめると、K要素分shiftさせて、全体にXOR xした結果がBと一致するかを判定したい。
これを判定するにはいくつかの知見を持っている必要がある。
段階的に考えていこう。

XOR xがない場合、つまり、AをK要素分shiftさせた結果とBが等しくなるかを判定する方法を考えよう。
これは、選択肢が色々ある。A+A+[inf]+Bのように配列を結合させて、KMPをやってもいいし、
A+AとBに対してローリングハッシュを作って比較してもいい。
どちらにしろ、何が言いたいかというと、A+Aのように2個分くっつけることで、
shiftを考えるのではなく、ある区間がBと一致するかという問題で考えることができるということである。
これはshift問題に取り組むときに実装量を減らすため、よく使われるテクである。

今回の問題はこれに区間XORが追加される。
区間に一定の操作を行うことへの対処法はいくつかテクがあるが、その中でも階差を用いる方法を使おう。
これは和で考えると分かりやすいが、
1 2 3 4
に対する階差は
1 1 1
であるが、2から4に+2するとすると、階差の最初の1を+2するだけで実現できる。
3 1 1
とすると、最初が1であることから、
1 4 5 6
の状態を表していることが分かる。
これをXORでも行う。

A2[i] = A[i] xor A[i + 1]
B2[i] = B[i] xor B[i + 1]
として階差を取っておこう。
すると、
A[i]以降にXOR xをするには、A2[i-1]にXOR xをするだけでよくなる。
しかも、この階差を取っておくことで、区間が等しいかというのも判定することが、できる。
A[i..i+K-1] = B[j..j+K-1] が成り立つことと A[i]=B[j] かつ A2[i..i+K-2]=B2[j..j+K-2]が成り立つことは同義である。
しかもA[i]=B[j]となるようにXOR xを考えているため、実際はA2[i..i+K-2]=B2[j..j+K-2]が成り立つことだけ考えればいい。
もう既にxの値は関係なく、階差を取ったときにA2[i..i+K-2]=B2[j..j+K-2]が成り立つことを判定すればよくなる。
これは、同様にKMPでもローリングハッシュでもよい。
これで答えが求まる。

int N, A[201010], B[201010], A2[201010], B2[201010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
    rep(i, 0, N) cin >> B[i];

    rep(i, 0, N) A2[i] = A[i] ^ A[(i + 1) % N];
    rep(i, 0, N) B2[i] = B[i] ^ B[(i + 1) % N];

    vector<int> v;
    rep(i, 0, N) v.push_back(A2[i]);
    rep(i, 0, N) v.push_back(A2[i]);
    rep(i, 0, N) v.push_back(B2[i]);

    RollingHash rh;
    rh.init(v);

    rep(k, 0, N) if (rh.hash(k, k + N - 2) == rh.hash(N * 2, N * 2 + N - 2)) {
        int x = A[k] ^ B[0];
        printf("%d %d\n", k, x);
    }
}