[AtCoder] ABC 171 E – Red Scarf

2020年7月21日

問題

方針

排他的論理和 xor を \( \oplus \) で表現します。\( i \) 番目のスカーフの番号を \( b_i \) とすると、

\[ a_i = b_1 \oplus b_2 \oplus \cdots  \oplus b_{i-1} \oplus a_{i+1} \oplus \cdots \oplus b_{N}\]

ここで、\( a_i \) の排他的論理和を考えます。

\begin{eqnarray}
a_1 \oplus \cdots \oplus a_{N} &=& (b_1 \oplus \cdots \oplus b_1) \oplus \cdots \oplus(b_N \oplus \cdots \oplus b_N)\\
&=& b_1 \oplus \cdots \oplus b_N
\end{eqnarray}

となります。これは、\( b_i \oplus b_i = 0 \) と \( b_i \oplus 0 = b_i \) と \( N \) が偶数であることを利用して導けます。

また、

\begin{eqnarray}
a_1 \oplus \cdots \oplus a_{N}\oplus a_1 &=& b_1 \oplus \cdots \oplus b_N \oplus (b_2 \oplus \cdots \oplus b_N)\\
&=& b_1
\end{eqnarray}

となるので、任意の \( b_i \) について求めることができます。

コード