問題概要

1 個の正の整数 $N$ が与えられる。次の条件を満たす整数 $a, b$ が存在するような整数の組 $u, v$ の個数を 1000000007 で割った余りを求めよ。

$a$ xor $b$ = $u$
$a + b = v$

制約

$1 \le N \le 10^{18}$

考えたこと

いかにも桁 DP の問題。次のような配列 dp を考えたくなる。

dp[i][0]：上から $i$ 桁目まで考えたときの、その和がちょうど $N$ と一致するような $a, b$ に対する、組 $(u, v)$ の個数
dp[i][1]：上から $i$ 桁目まで考えたときの、その和が $N$ より小さいような $a, b$ に対する、組 $(u, v)$ の個数

しかし、たとえば上から $i$ 桁目について考えているときに、 $a, b$ の上から $i$ 桁目の値をともに 1, 1 とすると、和をとったときに繰り上がりが発生する。

よって、次のように修正することにする。

dp[i][0]：上から $i$ 桁目まで考えたときの、その和がちょうど $N$ と一致するような $a, b$ に対する、組 $(u, v)$ の個数
dp[i][1]：上から $i$ 桁目まで考えたときの、その和が $N$ よりちょうど 1 だけ小さいような $a, b$ に対する、組 $(u, v)$ の個数
dp[i][2]：上から $i$ 桁目まで考えたときの、その和が $N$ より 2 以上小さいような $a, b$ に対する、組 $(u, v)$ の個数

こうすれば、繰り上がりを考慮してもなお、遷移を作ることができる。計算量は $O(\log N)$ となる。

コード

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;

int main() {
    long long N;
    cin >> N;

    // 0: 一致, 1: -1, 2: -2 以下
    vector<long long> dp(3, 0);
    dp[0] = 1;
    for (int d = 61; d >= 0; --d) {
        bool ichi = (N >> d) & 1;
        vector<long long> nex(3, 0);

        // from 0 (一致)
        if (ichi) {
            nex[0] += dp[0];  // (0, 1)
            nex[1] += dp[0];  // (0, 0)
        } else nex[0] += dp[0];  // (0, 0)

        // from 1 (-1)
        if (ichi) {
            nex[1] += dp[1];  // (1, 1)
            nex[2] += dp[1] * 2;  // (0, 0), (0, 1)
        } else {
            nex[0] += dp[1];  // (1, 1)
            nex[1] += dp[1];  // (0, 1)
            nex[2] += dp[1];  // (0, 0)
        }

        // from 2 (-2 以下)
        nex[2] += dp[2] * 3;  // (1, 1), (0, 1), (0, 0)

        // swap
        for (int i = 0; i < 3; i++) nex[i] %= MOD;
        swap(dp, nex);
    }
    cout << (dp[0] + dp[1] + dp[2]) % MOD << endl;
}