123 Triangle [AtCoder Grand Contest 043 B]

https://atcoder.jp/contests/agc043/tasks/agc043_b

解説

https://atcoder.jp/contests/agc043/submissions/11065208

まず、答えは0,1,2の3択になる。
このどれが答えになるかを求めていこう。
これは実験すると分かるし、操作を見てみるとそうなりそうなこともわかる。

次の一手を生み出すのがきつい。
答えの偶奇をまずは特定しよう。
答えの偶奇を見たいので、Aも偶奇だけを見てやればよさそう。
つまり、すべての差の計算をmod 2で計算した場合を考える。
mod 2での計算結果なので、最初のAもmod 2をして、0/1で考えて問題ない。

mod 2上では、x+yもx-yもx xor yもすべて同じ結果になる。
試してみればわかる。
よって、操作はx+yとしているのと同じ状況になる。
この問題は典型問題であり、パスカルの三角形を使って高速に計算ができる。
N要素ある時、操作後の最終的な値は C(N-1,i)*A[i]の総和 となる（i=0,1,...,N-1）。

よって、C(N-1,i)の偶奇が分かれば、最終的な値の偶奇もわかる。

これはインターネットで「二項係数 偶奇」で調べると、
二項係数の偶奇(解決編) - 球面倶楽部 零八式 mark II
こんな良いサイトが出てくる。

C(n,r)%2==1 <=> n == ( r | (n - r) ) がtrue  

ということらしいので、これが成り立つならば、A[i]が足される。
mod 2なので、操作はx^yであると考えて、総和の代わりにxor和を使って、
二項係数が奇数であればxor 1をしている。
これで最終的に1であれば、答えは奇数なので1を答える。

次に、0か2かの判定であるが、1が含まれるのであれば答えは0となる。
これは実験をしてみると何となく分かる。
実験からエスパーしよう。

そうでないなら、Aは0と2から構成される。
0と2の操作を見てみると、0と0は0, 0と2は2, 2と0は2, 2と2は2であるため、xor操作になっている。
なので、さっきと同様にC(N-1,i)の偶奇を使って、最終的な値の偶奇を計算して、答える。

int N, A[1010101];
//---------------------------------------------------------------------------------------------------
int solve() {
    rep(i, 0, N - 1) A[i] = abs(A[i] - A[i + 1]);
    N--;

    int tot = 0;
    rep(i, 0, N) if (A[i] == 1 && (i | (N - 1 - i)) == N - 1) tot ^= 1;
    if (tot) return 1;

    rep(i, 0, N) if (A[i] == 1) return 0;

    tot = 0;
    rep(i, 0, N) if (A[i] == 2 && (i | (N - 1 - i)) == N - 1) tot ^= 2;
    return tot;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N; string S; cin >> S;
    rep(i, 0, N) A[i] = S[i] - '0';
    cout << solve() << endl;
}