LightOJ - 1032 Fast Bit Calculations (数位DP)

#include <cstdio>
#include <cstring>

int num[50];
long long dp[50][2];
long long nowx;

long long dfs(int i, int d, bool isQuery) {
    if (i == 1) {
        return 0;
    }
    long long &nowdp = dp[i][d];
    if (!isQuery && ~nowdp) return nowdp;
    int end = isQuery?num[i-1]:1;
    long long ans = 0;
    for (int j = 0; j <= end; j++) {
        ans += dfs(i-1, j, isQuery && j==end);
        if (d == 1 && j == 1) {
            ans += isQuery?(nowx%(1<<(i-2))+1):(1<<(i-2));
        }
    }
    if (!isQuery) nowdp = ans;
    return ans;
}

long long cal(long long x) {
    nowx = x;
    if (x == 0) return 0;
    int len = 0;
    while (x) {
        num[++len] = x%2;
        x>>=1;
    }
    return dfs(len+1, 0, true);
}

int main() {
    int t;
    scanf("%d", &t);
    int cas = 1;
    memset(dp, -1, sizeof(dp));
    while (t--) {
        long long n;
        scanf("%lld", &n);
        printf("Case %d: %lld\n", cas++, cal(n));
    }
    return 0;
}