Submission #7077605

---

Source Code Expand

#include <bits/stdc++.h>
using i64 = long long;

constexpr i64 mod = 1000000007;

i64 n;
i64 dp[61][2][2][2];

// i桁以下の場合の数, N以下が確定しているか, i-th bitがk, i-th bitがmarkedか
i64 rec(int i, int j, int k, int l) {
    if (dp[i][j][k][l] >= 0) return dp[i][j][k][l];
    i64 ret = 0;
    if (i == 0) {
        if (!j && (n & 1) == 0 && k) ret = 0;
        else if (l && k) ret = 0;
        else ret = 1;
        return dp[i][j][k][l] = ret;
    }
    // 1, marked
    if ((j || ((1ll << (i - 1)) & n)) && (k || l)) {
        ret = rec(i - 1, j, 1, 1);
    }
    // 1, not marked
    if ((j || ((1ll << (i - 1)) & n)) && !(k && l)) {
        ret = (ret + rec(i - 1, j, 1, 0)) % mod;
    }
    // 0, marked
    if (k || l) {
        ret = (ret + rec(i - 1, ((1ll << (i - 1)) & n) || j, 0, 1)) % mod;
    }
    // 0, not marked
    if (!(k && l)) {
        ret = (ret + rec(i - 1, ((1ll << (i - 1)) & n) || j, 0, 0)) % mod;
    }
    return dp[i][j][k][l] = ret;
}

int main() {
    std::cin >> n;
    for (auto &a : dp) for (auto &b : a) for (auto &c : b) for (auto &e : c) e = -1;
    std::cout << rec(60, 0, 0, 0) << std::endl;

    return 0;
}

Submission Info

Judge Result