题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3709
也是一道基础的数位DP题目，用dp[i][j][k]记录枚举到第i位时，以j为中心的和为k的种数有多少，以DFS记忆化搜索来记录，计算出以每一位为中心时的结果。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 2000+5;
typedef long long LL;
int bit[20];
LL dp[20][20][maxn];
LL dfs(int len, int o, int l,int ismax)
{if(len == -1) return l == 0;if(l < 0) return 0;if(!ismax && dp[len][o][l]!=-1) return dp[len][o][l];LL ans = 0;int Max = ismax? bit[len]:9;for(int i=0; i<=Max; i++)ans += dfs(len-1, o, l+(len-o)*i, ismax&&i==Max); return ismax? ans : dp[len][o][l]=ans;
}
LL solve(LL n)
{int len = 0;while(n){bit[len++] = n%10;n /= 10;}LL ans = 0;for(int i=0; i<len; i++) ans += dfs(len-1, i, 0, 1);return ans-(len-1);
}
int main()
{int T;scanf("%d", &T);memset(dp,-1,sizeof(dp));while(T--){LL L,R;cin >> L >> R;cout << solve(R)-solve(L-1) << endl;}return 0;
}