Submission #1518384

---

Source Code Expand

#include <bits/stdc++.h>
#include <math.h>
#define uint unsigned long long
#define ll long long
#define db double
#define ls rt << 1
#define rs rt << 1 | 1
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define X first
#define Y second
#define pcc pair<char, char>
#define vi vector<int>
#define vl vector<ll>
#define rep(i, x, y) for(int i = x; i <= y; i ++)
#define rrep(i, x, y) for(int i = x; i >= y; i --)
#define ept 1e-9

using namespace std;
inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}
const int mod = 1e9 + 7;
ll N;
map<ll,ll> DP;
ll dp(ll x)
{
    if(DP[x]) return DP[x];
    return DP[x] = ( dp(x / 2) + dp((x - 1) / 2) + dp((x - 2) / 2) )%mod;
}
int main()
{
    DP[0] = 1;
    DP[1] = 2;
    cin >> N;
    cout << dp(N) << endl;
    return 0;;
}

Submission Info

Judge Result