ABC050 D(ARC066 B) : Xor Sum

問題リンク atcoder.jp

問題概要

$a \, xor \, b= u, a + b = v \,\,(1 \leqq u,v \leqq N)$を満たす$(u,v)$の組の個数をmod $10^{9}+7$で求めよ

解法

$(u,v)$ではなく$(a,b)$を数えることを考えます。
そのままでは$(u,v) = (5,9)$に対して$(a,b) = (7,2)$や$(a,b) = (6,3)$など複数通り考えられてしまうので、正しく数えられません。
アルメリアさんの記事を参照すると$(u,v)$から$(a,b)$への1対1の対応づけが分かると思います。
具体的には$a$と$b$とであるビットの値が異なる場合、必ず$a$に1を立てて$b$を0とすることで一通りに定まります。
先ほどの$(u,v) = (5,9)$に対応する唯一の$(a,b)$を$(a,b) = (7,2)$に限定しています。

$a,b$の下から$i$番目のビットを$a_i, b_i$と表すことにします。
このとき、必ず$(a_i, b_i) = (0,0)\,or\,(1,0)\,or\,(1,1)$となります。
桁dpで解くのですが、数字として考慮する対象は$v$として、各$v$に対して$(a,b)$が何通りあるかを考えることにします。
$v \leqq N$のとき、必ず$u \leqq N$となるので、$v$のみを考えて数え上げた$(a,b)$の数は全て条件を満たすことになります。
桁dpを行う際は各ビットについて$(0,0)\,or\,(1,0)\,or\,(1,1)$のいずれかを選択していく形をとります。(何も条件の縛りがないと$3^{桁数}$ということになります)
桁dpを行う上で欲しい状態は以下の3つです。

• 現在何桁目か
• 繰り上がりが存在するか(繰り上がりは必ず0 or 1なので状態数は2)
• 暫定$N$より大きいか(下から見るので常に現在見ているビットが数の大小に大きく関わります)

遷移を一つづつ考えます。
①$(a_i,b_i)=(0,0)$
次の桁への繰り上がりはありません。下位ビットからの繰り上がりがあるときには、出来上がる$v_i$には1が立つということになります。

②$(a_i,b_i)=(1,0)$

• 下位ビットからの繰り上がりがあるとき、繰り上がりがあり、$v_i$は0となります。

• 下位ビットからの繰り上がりがないとき、繰り上がりはなく、$v_i$は1となります。

③$(a_i,b_i)=(1,1)$

• 下位ビットからの繰り上がりがあるとき、繰り上がりがあり、$v_i$は1となります。

• 下位ビットからの繰り上がりがないときも繰り上がりがあり、$v_i$は0となります。

暫定$N$より大きいかのフラグについて

例えば$N=10$で3ビット目を見ているとき、それまでが**11になっていたとします。10は2進数で"1010"なので、この状態を暫定で$N$よりも大きいと表現しています(この先のどこか1箇所以上で$N$より小さい箇所が存在していなければならない)
$v_i$に1を立てる時、

• largerが確定している(フラグが1)とき→largerのまま

• largerフラグが0のとき→$N_i$($N$の$i$ビット目)が1ならばそのままフラグは0、$N_i$が0ならばフラグは1に変わる

といった遷移になります。$v_i$を0とするときも同様に考えることができます。

答え

最終的に欲しい値としては、繰り上がりはしておらず、$N$より大きくはない(つまり$N$以下)ので、
最後に答えるべき値は$dp[m][0][0]$($ m $は桁数(適当に60などとしておいてもよいです))となります。

実装

modintのライブラリ部分は省いています

mint dp[65][2][2]; //i番目,carry,larger

int main(){
    ll n; cin >> n;
    dp[0][0][0] = 1;
    rep(i,61){
        int v = n>>i & 1;
        rep(j,2) dp[i+1][0][v==0&j] += dp[i][0][j]; //0,0
        rep(j,2) dp[i+1][0][v==0|j] += dp[i][0][j]; //1,0
        rep(j,2) dp[i+1][1][v==0&j] += dp[i][0][j]; //1,1

        rep(j,2) dp[i+1][0][v==0|j] += dp[i][1][j]; //0,0
        rep(j,2) dp[i+1][1][v==0&j] += dp[i][1][j]; //1,0
        rep(j,2) dp[i+1][1][v==0|j] += dp[i][1][j]; //1,1
    }
    cout << dp[61][0][0] << "\n";
}