- 1#include
- 2#include
- 3#include
- 4#include
- 5#include 6#include
- 7#include
- 8#include
- 9#include
- 10 #definell __int6411 #definedazhi 214748364712 #definebug() printf("!!!!!!!")13 #defineM 10000514 using namespace std;
- 15 ll a,b;
- 16ll f[30][30][2005];
- 17 intbit[30];
- 18ll dp(intpos,intx,intst,int flag)
- 19 {
- 20 if(pos==0)returnst==0;
- 21 if(st<0)return 0;
- 22 if(flag&&f[pos][x][st]!=-1)return f[pos][x][st];
- 23 intd=flag9:bit[pos];
- 24ll re=0;
- 25 for(inti=0;i<=d;i++)
- 26 {
- 27re+=dp(pos-1,x,st+i*(pos-x),flag||i!=d);
- 28 }
- 29 if(flag) f[pos][x][st]=re;
- 30 return re;
- 31 }
- 32 ll fun(ll n)
- 33 {
- 34 if(n<0)return 0;
- 35 intlen=0;
- 36 while(n>0)
- 37 {
- 38bit[++len]=n%10;
- 39n/=10;
- 40 }
- 41ll ans=0;
- 42 for(inti=1;i<=len;i++)
- 43 {
- 44ans+=dp(len,i,0,0);
- 45 }
- 46 returnans-len+1;
- 47 }
- 48 int main()
- 49 {
- 50 int t;
- 51scanf("%d",&t);
- 52memset(f,-1,sizeof(f));
- 53 while(t--)
- 54 {
- 55scanf("%I64d %I64d",&a,&b);
- 56printf("%I64d\n",fun(b)-fun(a-1));
- 57 }
- 58 return 0;
- 59}
来源: http://www.bubuko.com/infodetail-1995078.html