AGC043 B - 123 Triangle

問題：B - 123 Triangle

解答：Submission #11073495 - AtCoder Grand Contest 043

解法：a[i]を-1して各要素を0, 1, 2で考える。各ステップに現れる数字も0, 1, 2のいずれかであり、最終的な数字も0, 1, 2のいずれかである。

ここで、次のような場合分けが重要である。

1. a[i]に1が含まれている
2. a[i]に1が含まれていない

1.の場合は、最終的な数字は2になりえない。2.の場合は、最終的な数字は1になりえない。よって下記のような操作を考えればよい。

1. 2を0にして考え、各項をmod2で足し続ける
2. 2を1にして考え、各項をmod2で足し続け、足し続けた結果を2倍する

足し続けた結果は実験により、二項係数を用いてn-1C0 * a[0] + n-1C1 * a[1] + ... + n-1Cn-1a[n-1] のmod2となる。nCkの偶奇は(n & k == k)なら奇数、それ以外は偶数である。よってこの問題が解けた。