Light OJ 1032

数位dp，许多数位dp需要统计某种模式（子串）出现的数量，这种题通常需要在递归参数中加入高位已经出现过的模式的数量。

#include <cstdio>
#include <cstring>
using namespace std;

#define D(x) 

const int MAX_DIGIT = 40;

long long n;
int f[MAX_DIGIT];
long long memoize[MAX_DIGIT][2][MAX_DIGIT];
int cnt;

int to_digits(long long a)
{
    int ret = 0;
    while (a > 0)
    {
        f[ret++] = a % 2;
        a /= 2;
    }
    return ret;
}

long long dfs(int digit, bool less, bool last, int adj_num)
{
    D(cnt++);
    if (digit < 0)
    {
        return adj_num;
    }
    if (less && memoize[digit][last][adj_num] != -1)
    {
        return memoize[digit][last][adj_num];
    }
    int limit = less ? 1 : f[digit];
    long long ret = 0;
    for (int i = 0; i <= limit; i++)
    {
        int delta = (i == 1 && last) ? 1 : 0;
        ret += dfs(digit - 1, less || i < f[digit], i == 1, adj_num + delta);
    }
    if (less)
    {
        memoize[digit][last][adj_num] = ret;
    }
    return ret;
}

long long work(long long n)
{
    if (n < 0)
    {
        return 0;
    }
    if (n == 0)
    {
        return 0;
    }
    int len = to_digits(n);
    cnt = 0;
    return dfs(len - 1, false, false, 0);
}

int main()
{
    int t;
    scanf("%d", &t);
    memset(memoize, -1, sizeof(memoize));
    for (int i = 1; i <= t; i++)
    {
        int a;
        scanf("%d", &a);
        printf("Case %d: %lld
", i, work(a));
        D(printf("%d
", cnt));
    }
    return 0;
}