1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <cmath>
#include <map>
using namespace std;
int dp(int N, int K, map<pair<int, int>, int>& valMap) {
    if (N == 0) {
        return 1;
    }
    if (N < 0 || N > (1 << (K + 2)) - 2) {
        return 0;
    }
    auto iter = valMap.find(make_pair(N, K));
    if (iter != valMap.end()) {
        return iter->second;
    }
    else {
        int ans = dp(N, K - 1, valMap) + dp(N - (1 << K), K - 1, valMap) + dp(N - (1 << (K + 1)), K - 1, valMap);
        valMap[make_pair(N, K)] = ans;
        return ans;
    }
}
int main() {
    int N;
    cin >> N;
    int len = log2(N);
    map<pair<int, int>, int> valMap;
    cout << dp(N, len, valMap) << '\n';
    return 0;
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX