AtCoder ABC 050 D - Xor Sum (ARC 066 D) (2D, 橙色, 600 点)

繰り上がりがあるから、ただの「桁 DP」よりは難しい。でも少しの工夫で解ける！

• 問題へのリンク

問題概要

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

• xor =
• 

制約

• 

考えたこと

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

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

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

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

---

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

---

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

コード

#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;
}