この問題を難しくしている原因は、通常の整数の足し算と「繰り上がりのない足し算」である XOR が混在していることです。漸化式にある足し算を二進表記の筆算で行うとしたとき、もしも繰り上がりが起こらなければ \(+\) と \(\oplus\) は等価になり、問題はずっと簡単になります。繰り上がりが起こらないのは \(A,B,C\) を二進表記したときの立っている bit の集合と同一視したときに \(C\subset A,B\) となることと同値で、この場合は \(X\) は最小とは限らない周期として \(3\) を持ち、答えを簡単に計算できます。

さて、一般の \(A,B,C\) においては \(X\) には周期が存在しないことが証明できます。そこで、繰り上がりの影響を詳しく解析します。

任意の非負整数 \(d\) に対して漸化式 \(X_{n+2}=(X_i\oplus X_{i+1})+C\) が \(\text{mod } 2^{d+1}\) で意味を持っていることに注目しましょう。 \(X\) の要素の二進表記を考えて \(X_N\) の \(d\) bit 目を計算する問題に読み替えます。

列 \(X\bmod 2^{d+1}\) は有限個の値を取るため周期を持ちますが、実は最小とは限らない周期として \(3\times 2^d\) を持つことが示せます。よって \(X\bmod 2^{d+1}\) を考える際には長さ \(3\times 2^d\) の配列を保持していれば十分です。さて、漸化式は \(X_n,X_{n+1}\) から \(X_{n+2}\) を得る方法を与えていましたが、発想を変えて \(X\bmod 2^{d+1}\) から \(X\bmod 2^{d+2}\) を得る方法を考えてみましょう。つまり、長さ \(3\times 2^d\) の配列と \(A,B,C\) を受け取って長さ \(3\times 2^{d+1}\) の配列を返す関数をなんとか設計してみましょう。

これを考えるには、繰り上がりの情報が必要です。そこで、 \(X\bmod 2^{d+1}\) の代わりに次の \(2\) つの \(01\) 配列を保持することにしましょう。

• \(X\) の \(d\) bit 目を並べた長さ \(3\times 2^d\) の配列 \(X^d\)
• \(X\) の \(d-1\) bit 目の計算で発生する繰り上がり bit を並べた長さ \(3\times 2^{d-1}\) の配列 \(Y^{d-1}\)

\((X^d,Y^{d-1})\) から \((X^{d+1},Y^d)\) を得るのは簡単です。その方法をよく観察すると \(Y^{d-1}\) のみから \(Y^d\) を得ることも可能で、 \(Y^{d-1}\) から \(X^d\) を計算できることもわかります。

このままでは \(Y^d\) の長さが大きくなりすぎる問題がありますが、 \(A,B,C\lt 2^{20}\) の制約から \(Y^d\) に含まれる \(1\) の個数がひどく大きくなることはないことが示せます。そこで \(Y^d\) の代わりに \(Y^d\) で \(1\) になっている要素の添字を並べた列 \(I^d\) を保持することにします。

最後に \(I^d\) の要素としては \(N\) 以下の値のみ保持すればよく、 \(d\) を現実的な回数増やせばいずれ \(I^d\) は空になり、それ以降も空であることが示せます。このことは \(X_N\) の \(d\) bit 目がそれ以降は \(0\) であることを意味します。以上を実装すれば比較的高速な解法が得られます。

詳細な解説については こちら をご確認ください。