[AtCoder] エイシング プログラミング コンテスト 2020 D – Anything Goes to Zero

問題

方針

ビットカウントのアルゴリズム

アルゴリズムについては上記のサイトを参考にしました。

\( 2 \times 10^5 \) 以下の \( f(n) \) の値は、愚直に求めます。

ビット毎に剰余を取る

\( X \) のビットカウントを \( p\) とすると、\( X \) の \( i \) ビット目を反転させたときのビットカウントは、\( p – 1 \) または \( p + 1 \) となります。また、剰余はビット毎に演算しても良いので、\( X \) の \( p – 1 \) と \( p + 1 \) の剰余をあらかじめ計算し、\( i \) ビット目の値によって補正すれば良いです。

ビット毎に剰余を取るには、階乗の剰余のアルゴリズムを使えば良いです。注意として、\( p = 1 \) のとき、\( X_i = 1 \) ならば、答えは \( 0 \) となります。

ビット反転の補正

\( a_1 =  X \bmod (p – 1) \) 、\( a_2 = X \bmod (p + 1) \) とします。これらはあらかじめ求めておきます。

\( X_i = 1 \) のとき

このとき、\( X_i = 0 \) としたときの、\( p – 1 \) による剰余は、

\[(a_1 – 2^{N – i – 1} \bmod (p – 1) + p – 1) \bmod (p – 1)\]

となります。

\( X_i = 0 \) のとき

このとき、\( X_i = 1 \) としたときの、\( p + 1 \) による剰余は、

\[(a_2 + 2^{N – i – 1}) \bmod (p + 1)\]

となります。

コード