[Codeforces] Codeforces Round #672 (Div. 2) B. Rock and Lever

2020年10月12日

問題

方針

自然数 \( a, b \) が

\[ a \ \& \ b \geq a \oplus b\]

を満たすとき、\( 2^{i} \leq a, b \leq 2^{i+1} -1 \) を満たす \( i \) が存在します。これは同じビット数で表現できる数は、最高位のビットがともに \( 1 \) なので、\( a \oplus b \) の最高位のビットは \( 0 \) となるからです。一方で、異なるビット数の論理積は最高位のビットが \( 0 \) となり、排他的論理の最高位のビットは \( 1 \) となります。

したがって、\( 2^i \leq a_j \leq 2^{i + 1} – 1\) となる \( a_j \) の数を \( m \) とすると、

\[ \dfrac{m(m-1)}{2}\]

個のペアが存在ます。与えられた数列の順序を入れ替えても影響はないので、昇順に整列させてペアを数え上げます。

コード