Article From:https://www.cnblogs.com/linxif2008/p/9906467.html

# Lough Valley P4999 Annoying Mathematics Homework

Main idea of the title:

Record the sum of the number of a number and the sum of each number for him. For example, the sum of 123 numbers is 1 + 2 + 3 = 6.

Now, given the interval [l, r], the number sum of all integers in the interval is obtained.

Train of thought:

This is a very standard digital DP problem.

The specific approach is not very good to describe, or first code it…

My comments are abstract too. I haven’t learned the advice of digital dp. First, I’ll learn digital dp.

CODE：

```#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define MOD 1000000007
typedef long long int lli;
const lli N={0,45,900,13500,180000,2250000,27000000,315000000,599999979,499999720,999996857,999965357,999622007,995905007,955900007,527500007,960000042,450000378,3969,41895};
const lli P={1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,10000000000,100000000000,1000000000000,10000000000000,100000000000000,1000000000000000,10000000000000000,100000000000000000,1000000000000000000};
//The above two lines are for table-typing, which is convenient for DP calculation.//NiRepresenting [0,10i)The sum of all integers//pThe number assembly is 10 K power.lli i,j,k,m,n,ans,t,r,tmp;
lli nums;
lli dfs(int pos,bool flag){  //I don't use recursion, so I wrote a recursion.                             //posIt's DP to number one, flag is whether this one has an upper bound or not.if(!flag){
return N[pos];//If there is no upper bound, all integers with this one can be retrieved, then the values in the table can be returned directly.}if(pos==0) return 0;//Numbers with the highest number being the 0th and apparently zeroLLI ans=0;
for(int i=0;i<=nums[pos];i++){
if(i==nums[pos]){//If this one has an upper bound, it means that all integers that do not complete this one can not be obtained.Ans=(ans+dfs(pos-1,true))%MOD;
ans=(ans+((tmp%P[pos-1]+1)*nums[pos])%MOD)%MOD;
}else{//If this one has no upper boundAns=(ans+dfs(pos-1,false))%MOD;
ans=(ans+P[pos-1]*i)%MOD;
}
}
return ans;
}
lli count(lli x){
int len=0;
tmp=x;
while(x) nums[++len]=x%10,x/=10;
return dfs(len,true);
}
int main(){
scanf("%lld",&t);
for(r=1;r<=t;r++){
scanf("%lld%lld",&n,&m);
j=count(m);
k=count(n-1);
ans=(MOD+j-k)%MOD;
printf("%lld\n",ans);
}
return 0;
}```