solution.h

/*
Code generated by https://github.com/goodstudyqaq/leetcode-local-tester
*/
#if __has_include("../utils/cpp/help.hpp")
#include "../utils/cpp/help.hpp"
#elif __has_include("../../utils/cpp/help.hpp")
#include "../../utils/cpp/help.hpp"
#else
#define debug(...) 42
#endif

template <class T>
auto vect(const T& v, int n) { return vector<T>(n, v); }
template <class T, class... D>
auto vect(const T& v, int n, D... m) {
    return vector<decltype(vect(v, m...))>(n, vect(v, m...));
}

template <typename T>
static constexpr T inf = numeric_limits<T>::max() / 2;
mt19937_64 mrand(random_device{}());
long long rnd(long long x) { return mrand() % x; }
int lg2(long long x) { return sizeof(long long) * 8 - 1 - __builtin_clzll(x); }

#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

typedef pair<int, int> pii;
typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;


class Solution {
   public:
    int findIntegers(int n) {
        vector<int> v;
        while (n) {
            v.push_back(n % 2);
            n /= 2;
        }
        reverse(v.begin(), v.end());
        auto dp = vect(-1, v.size(), 2);       
        function<int(int, int, bool)> dfs = [&](int idx, int one, bool limit) -> int {
            if (idx == v.size()) return 1;
            if (!limit && dp[idx][one] != -1) return dp[idx][one];
            int LIMIT = limit ? v[idx] : 1;
            int ans = 0;
            if (one) {
                // 0
                ans = dfs(idx + 1, 0, limit & (LIMIT == 0));
            } else {
                // 0
                ans = dfs(idx + 1, 0, limit & (LIMIT == 0));
                if (LIMIT == 1) {
                    ans += dfs(idx + 1, 1, limit & (LIMIT == 1));
                }
            }
            if (!limit) dp[idx][one] = ans;
            return ans;
        };
        return dfs(0, 0, true);
    }
};