数位DP模板

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

int t;
long long dp[19][19][2005];
long long l, r;
int digit[20];

long long dfs(int len,...int if4..., bool limit)
{
    if (len == 0)
        return 1; //个位
    if (!limit && dp[len][...])
        return dp[len][...];  //dp数组的内容应和dfs调用参数的内容相同，除了是否达到上限
    long long cnt = 0;
    int up_bound = (limit ? digit[len] : 9);
    for (int i = 0; i <= up_bound; i++)
    {
        if(...) continue; //剪枝
        ...;
        cnt += dfs(len-1, ..., limit && i == up_bound);
    }
    if (!limit) //完整状态
        dp[len][...] = cnt;
    return cnt;
}

long long solve(long long x)
{
    int k = 0;
    while (x)
    {
        digit[++k] = x % 10;
        x /= 10;
    }
    return dfs(k,...,1)
}

int main()
{
        memset(dp, 0, sizeof(dp));
        scanf("%lld%lld", &l, &r);   //有些题目其实并不需要用到long long
        printf("%lld
", solve(r) - solve(l - 1)); //只有满足区间减法才能用
    return 0;
}