题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=3709
枚举支点位置就好了
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxp=21;
typedef long long LL;
LL d[maxp][maxp][1601];
int digit[maxp];
LL DFS(int pos,int point,int preSum,bool limit)
{ //当前位置| 支点位置| 前面的和| 是否在上界if(pos==-1) return preSum==0;if(preSum<0) return 0;LL& ans=d[pos][point][preSum];if(!limit && ans!=-1) return ans;LL temp=0;int up=limit?digit[pos]:9;for(int i=0;i<=up;i++)temp+=DFS(pos-1,point,preSum+(pos-point)*i,limit&&i==up);if(!limit) ans=temp;return temp;
}
LL solve(LL x){int len=0;while(x){digit[len++]=x%10;x/=10;}LL ans=0;for(int i=0;i<len;i++) //因为每次DFS都会计算全为0的情况，所以ans要减去(len-1)ans+=DFS(len-1,i,0,true);return ans-len+1;
}
int main(int argc, char const *argv[])
{int T; LL s,e;scanf("%d",&T);memset(d,-1,sizeof(d));while(T--){scanf("%lld%lld",&s,&e);if(s==0) cout<<solve(e)<<endl;else cout<<solve(e)-solve(s-1)<<endl;}return 0;
}