Article From:

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.


#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define MOD 1000000007
typedef long long int lli;
const lli N[20]={0,45,900,13500,180000,2250000,27000000,315000000,599999979,499999720,999996857,999965357,999622007,995905007,955900007,527500007,960000042,450000378,3969,41895};
const lli P[19]={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[
25]; 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; }


Leave a Reply

Your email address will not be published. Required fields are marked *