B - Your Numbers are XORed... AtCoder Regular Contest 021

B - Your Numbers are XORed...
問題概略
数列Bnが与えられる。Bi = Ai ^ A(i+1)%n となるような辞書順最小の数列Aを出力せよ。

解法
xorはビットごとに計算が独立しているため、それぞれのビットについてA[0]のビットが0か1で成り立つかを見ていけば良い。
O(10^5 *32)
辞書順最小のため0優先(必ずA[0]=0らしいけど)
コード内のxorはすべて引き算的なニュアンス
a ^ b = cのとき、a ^ c = b , b ^ c = aのため、a ^ ? = b を満たす? をa ^ b = ? で求めている。
Submission #3145673 - AtCoder Regular Contest 021

  public static void solve() throws Exception {
        //longを忘れるなオーバーフローするぞ
        N = ni();
        A = nla(N);
        ArrayList<Integer> res = new ArrayList<>();
        for (int i = 33; i >= 0; i--) {
            boolean iok = false;
            for (int b = 0; b < 2; b++) {
                boolean start = b == 1;
                boolean now = start;
                for (int j = 0; j < N; j++) {
                    now = bget(A[j % N], i) ^ now;
                }
                if (start == now) {
                    res.add(b);
                    iok = true;
                    break;
                }
            }
            if (!iok) {
                System.out.println("-1");
                return;
            }
        }
        long sum = 0;
        for (Integer re : res) {
            sum *= 2;
            sum += re;
        }
        long v[] = new long[N];
        v[0] = sum;
        for (int i = 0; i < N - 1; i++) {
            v[i + 1] = A[i] ^ v[i];
        }
        print(v);
    }