PROBLEM LINK:
Setter Claudiu Babin
Tester Suchan Park
Editorialist Abhishek Pandey
DIFFICULTY:
Medium
PREREQUISITES:
Digit DP, Dynamic Programming (in general)
SYMBOLS USED:
There are lot of symbols used in this editorial, which are defined below.
Let me define the following variables
 UL= Upper Limit for x.
 i= Current Index in the number.
 i_{next}= Next index in the number
 D_{next}= The next digit we are placing at the next index.
 D= The digit we are considering placed at Current Index.
 E_{Next}= If after placing the next digit, is the number equal to UL if we consider all digits from Most Significant Digit to digits at the position we placed D_{next} at. This takes a value of 1 if equality holds, else 0. A value of 0 denotes that the number is < UL
 E= If considering digits from Most Significant Digit to D placed at Current Position, is my number equal to UL. Like above, takes value of 1 or 0 based on if equality holds. A value of 0 tells that the number is < UL
I know they are a lot of symbols, but we will be using them to denote things in the entire editorial, so please bear with me!
PROBLEM:
Given a function f as defined in the problem, find the value of f(x) for \forall x , x\in [L,R]
QUICKEXPLANATION:
Key to AC Realize that it is a classical Digit DP problem.
Realize that the value for f(x) for range [L,R] = Value of f(x) in range [1,R] Value of f(x) in range [1,L1]. Hence, we only need to implement this such that we are able to find all valid x \leq R, and then later reuse to find all valid x \leq L1 and subtract it from the answer.
Realizing this, define a 3D dp table of form dp[position][digit \ placed][equal \ or \ not].
With above defined, we can frame our dp recurrence as below, with obvious check of not making x > UL
 If D_{next}==D:
dp[i_{next}][D_{next}][E_{Next}] =\sum_{E=0}^{E=1} dp[i][D][E] as then no new block is formed. And contribution of older blocks is already computed in previous states.  If D_{next} \neq D:
dp[i_{next}][D_{next}][E_{Next}] =\sum_{D=0,D \neq D_{next}}^{D=9} \sum_{E=0}^{E=1} (dp[i][D][E] + Count \ of \ valid \ x\ with \ D_{next} \ at \ i_{next} * Appropriate \ power \ of \ 10 *D_{next}).
Appropriate power of 10 can easily be obtained from N_{UL}i where N_{UL} is number of digits in UL and i follows 1based indexing. With the power calculated, we can easily find 10^{N_{UL}i}. In terms of time complexity, it is better to precompute all required powers of 10 in O(N) in an array and later use it.
To find the count of valid x \leq UL considering things only upto index i, again, simply repeat the recurrence!!
Define num[index][digit][equal] as table and notice that
num[i_{next}][D_{next}][E_{Next}]= \sum _{D=0}^{D=9} \sum_{E=0}^{E=1} num[i][D][E]  with the obvious check that we are not making x > UL. Remember that I am starting from most significant digit, and considering all numbers that can be formed by considering things in range [0,i] only. The answer for index (i+1) will be calculated using our dp, and so do not worry about it right now!
The intuition of recurrence is can now be summarized as
I can place D_{next} at end of all valid x which
 End with any digit D which is less than UL already. ( E=0, D \in [0,9] \implies \sum _{D=0}^{D=9} num[i][D][0] )
 End with all digits \leq Digit at i’th position in UL if my number so far is equal to UL so far. Let the i’th digit at UL by D_i. So this case is for (E=1,D\in[0,D_i] \implies \sum_{D=0}^{D=D_i} num[i][D][1] )
With these 2 calculated, we can calculate the final answer and be done with the question! The final recurrence obtained is
 If D_{next}==D:
dp[i_{next}][D_{next}][E_{Next}] =\sum_{E=0}^{E=1} dp[i][D][E] as then no new block is formed. And contribution of older blocks is already computed in previous states.  If D_{next} \neq D:
dp[i_{next}][D_{next}][E_{Next}] =\sum_{D=0,D \neq D_{next}}^{D=9} \sum_{E=0}^{E=1} (dp[i][D][E] + num[i][D][E]* 10^{N_{UL}i} *D_{next}).
EXPLANATION:
First of all, if you are new to digit dp, or if the quick explanation felt completely alien to you, visit the Digit dp blog linked at Codeforces. This problem is pretty standard application of digit dp, so make sure to read and drill the prerequisites in your head .
Next thing, the quick explantion has everything needed to solve the problem. We will just get into the various “Why” and “How” of the stuff mentioned there and expand along those lines in the explanation.
You will very much benefit from the editorial if you are able to achieve the following
 Read and understand the digit dp blog at pre requisites.
 Understand a little dp in general. Classical problems like LIS, LCS are a good start.
Now, my hands had been itching to write a digit dp editorial since loong  simply because not a lot of good content is available on internet. So bear with me as this editorial is going to have many sections. We will discuss the following
 Some basic introduction to digit dp, followed by How do I know its digit dp? How do I break the query into Ans_{[L,R]} = Ans_{[1,R]} Ans_{[1,L1]}
 How do I know the number of states? How do I see what states I need?
 Figuring out the dprecurrence.
Cool and clear? Read the prerequisites if you’re new? Great, Lets begin!
Digit DP  Intro
The first thing I want to say here is, if you are one of those guys who feel that “Digit DP is some other branch of Dynamic Programming which I need to specifically learn” then just take a minute and throw that misconception into the nearest thrash can.
Digit dp is nothing but a normal dynamic programming. The only reason this got a separate name is because the same ideology/format is followed to solve a LOT of problems based on it. All that you need to learn this is understanding basic dynamic programming in first place, and then looking at the blog I linked in the pre requisites. If you know basic dynamic programming, you will realize that you are able to solve/invent digit dp solutions yourself without realizing it!
Now, onto how do I know that this was a digit dp question? Simple, because this question shares the common signs of a digit dp question! We need to tell if some numbers, in a huge range, satisfy some property or not. And frankly, no clear number theory stuff comes to mind, especially something which would run for numbers upto 10^{100000}. If you look at the link in prerequisite, you will notice similarities.
Now, the query part. I think we all agree that its trivial to see that since we want the sum of f(x) in range [L,R], we can easily break it down to sum of f(x) in range [1,R] sum of f(x) in range [1,L1].
States
Now, lets talk about states.
A very common question in all dynamic programming problems is that
“How do I know that its 1D dp, or 2D dp, or a 3D dp?”
Simple solution  Don’t think in terms of number of states! First, think of what things do you require to differentiate between all the states!
If you are reading this section, I assume we are clear on why it is a DP problem. So, jumping straight to the point, lets think of what things we need to know to be able to differentiate between the states
 Obviously the position where we are placing the digit matters. Placing a digit at somewhere near the starting of the number is different from placing it somewhere in middle etc.
 We also need to know what digit we are placing! For each digit, there are different contributions to the answer!
 Realize that we cannot place all digits from 09 just like that. We need to make sure that the number must be \leq UL or not! Hence, we also need to keep track of if the number became < UL already due to some previous digit we placed or if its still ==UL so far.
Hence, we get 3 states
 The position i , from [1,N]
 The digits d we are placing, from [0,9]
 If the number is still equal to UL or has become smaller than UL already  A boolean value having value [0,1]
Think over it a little, and see what we are able to see that we are able to differentiate between all the states in this manner. Also, note that the number of states is feasible! We just calculate answer for the state and use memoization.
DP Recurrence
Let us now discuss the DP Recurrence.
In quick explanation, we saw something as “Count of valid x \le UL with digit D_{next} at given index”. Lets first discuss this.
I will make one thing clear, its not a compulsion to make 2 tables here  we are doing that only for improved clarity. Exact number of dptables and states depend on what insights and observation you made and hence on the direction of your approach.
Lets make a table num[index][digit][equal\_\ or\_\ not] which denotes that "Number of numbers I can form considering digits in range [0,index], ending with “digit” with status of equality as defined in variable "equal \ or \ not"".
The recurrence for this is easy to derive!
Lets say I know the count of numbers ending with digit D \in[0,9] at index (i1). Let me denote it by G_{i1,D}. Similarly, count of numbers ending with digit D at index i is G_{i,D}.
We see the following easily
 If my number x has already become smaller than UL, then the count of numbers ending with digit D at index i is sum of numbers ending with any digit D_{prev} \in[0,9] at index (i1). Meaning, G_{i,D}= \sum_{D=0}^{D=9} G_{i1,D}
 If my number x has so far been equal to UL, then G_{i,D} = \sum_{D=0}^{D=D_i} G_{i1,D} where D_i is the corresponding digit at index i in UL. The intuition is same as above.
Now, how to comfortably implement it? The easiest hack is to include the state of equality in the dptable as well!
So let me define num[index][digit][equal\_\ or\_\ not] as G_{i,D,E} where each variable has same meaning as told in quick explantion.
Our recurrence just transforms to
 \large G_{i_{next},D_{next},E_{next}}= \sum_{D=0}^{D=9} G_{i,D,0} + \sum_{D=0}^{D=D_i}G_{i,D,1} where we know i_{next} , D_{next} and E_{next} when placing the next digit, and D_i is the corresponding digit at UL
With this calculated, all that is left is to simply do what the problem says!! Take some time to get this recurrence if you’re facing any doubts.
Create the final dp[index][digit][equal] table similar to above. Now, according to the question, 2 cases can arise
 D_{next} == D  For this case, no new contribution is done to the dptable as a block of digits cannot contribute multiple times. So we get dp[i_{next}][D_{next}][E_{Next}] =\sum_{E=0}^{E=1} dp[i][D][E]  with the check that x does not exceed UL

D_{next} \neq D  For this case, a new block is formed, so we add the appropriate contribution here. We get dp[i_{next}][D_{next}][E_{Next}] =\sum_{D=0,D \neq D_{next}}^{D=9} \sum_{E=0}^{E=1} (dp[i][D][E] + Count \ of \ valid \ x\ with \ D_{next} \ at \ i_{next} * Appropriate \ power \ of \ 10 *D_{next}).
The “syntax” or “format” of this dp recurrence is “Sum of previous contributions + Valid Count * Appropriate power of 10 * Digit we placed” Note that, we can simply pre compute the powers of 10 to use at start of our program, so its easily available. And the “Valid Count” is already calculated as seen in our previous discussion above.
The final answer for this can be easily extracted as \sum_{D=0}^{D=9} \sum_{E=0}^{E=1} dp[N_{UL}][D][E]. Note that our UL, as seen above in query decomposition part, is R and L1. To get answer for L1 even more easily, realize that you don’t need values of our table where E=1 , i.e. where x==L. The E=0 accounts for all x < L.
The setter has implemented it in a very neat, iterative manner. I’d like to encourage you to give a try, and then compare it with setter’s code given below
Setter''s DP
num[0][0][1] = 1;
for(int idx = 0;idx < sz(vec);idx++)
{
for(int digit = 0;digit < 10;digit++)
{
for(int equal = 0;equal < 2;equal++)
{
int idx_next = idx + 1;
for(int next_digit = 0;next_digit < 10;next_digit++)
{
if(equal && (next_digit > vec[idx])) break;
int equal_next = (equal & (next_digit == vec[idx]));
add(num[idx_next][next_digit][equal_next],num[idx][digit][equal]);
add(dp[idx_next][next_digit][equal_next],dp[idx][digit][equal]);
if(next_digit != digit) add(dp[idx_next][next_digit][equal_next],(((num[idx][digit][equal] * p[(sz(vec)  1  idx)]) % mod) * next_digit) % mod);
// ^^ if the next digit is equal to the current one, we shouldn't change the sum, else we should add 10^idx * next_digit.
}
}
}
}
SOLUTION
Setter
# pragma GCC optimize("Ofast")
# pragma GCC optimization ("unrollloops")
# include "bits/stdc++.h"
std::pair<int,int> DR[] = {{1,0},{0,1},{1,0},{0,1},{1,1},{1,1},{1,1},{1,1}};
# define ll long long
# define clock (clock() * 1000.0 / CLOCKS_PER_SEC)
# define rc(s) return cout << s,0
# define rcg(s) cout << s;exit(0)
# define _ ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
# define db(x) cerr << #x << " = " << x << '\n'
# define pb push_back
# define mp make_pair
# define all(s) s.begin(),s.end()
# define sz(x) (int)((x).size())
using namespace std;
// SOLUTION STARTS HERE
# define int ll
const int mod = 1e9 + 7;
int num[1 << 17][10][2],dp[1 << 17][10][2]; // dp[index][digit][equal_or_not]  the sum of f(x) up to index, such that the last digit is digit and it is still equal to the initial number iff equal_or_not == 1
int p[1 << 17];
int t;
void add(int &x,int val)
{
x += val;
if(x >= mod) x = mod;
}
pair<int,int>f(vector<int>vec) // pair<sum of all f less than x,sum of all f less than or equal to x>
{
for(int idx = 0;idx <= sz(vec);idx++)
{
for(int digit = 0;digit < 10;digit++)
{
for(int equal = 0;equal < 2;equal++)
{
dp[idx][digit][equal] = num[idx][digit][equal] = 0;
}
}
}
num[0][0][1] = 1;
for(int idx = 0;idx < sz(vec);idx++)
{
for(int digit = 0;digit < 10;digit++)
{
for(int equal = 0;equal < 2;equal++)
{
int idx_next = idx + 1;
for(int next_digit = 0;next_digit < 10;next_digit++)
{
if(equal && (next_digit > vec[idx])) break;
int equal_next = (equal & (next_digit == vec[idx]));
add(num[idx_next][next_digit][equal_next],num[idx][digit][equal]);
add(dp[idx_next][next_digit][equal_next],dp[idx][digit][equal]);
if(next_digit != digit) add(dp[idx_next][next_digit][equal_next],(((num[idx][digit][equal] * p[(sz(vec)  1  idx)]) % mod) * next_digit) % mod);
// ^^ if the next digit is equal to the current one, we shouldn't change the sum, else we should add 10^idx * next_digit.
}
}
}
}
pair<int,int>ans = {0,0};
for(int digit = 0;digit < 10;digit++)
{
ans = mp((ans.first + dp[sz(vec)][digit][0]) % mod,(ans.second + dp[sz(vec)][digit][0] + dp[sz(vec)][digit][1]) % mod);
}
return ans;
}
int32_t main(){_
//freopen("input","r",stdin);
p[0] = 1;
for(int i = 1;i <= 100005;i++) p[i] = (p[i  1] * 10) % mod;
cin >> t;
while(t)
{
int lnum,rnum;
string l,r;
vector<int>vecl,vecr;
cin >> lnum >> l;
cin >> rnum >> r;
for(auto it : l) vecl.pb(it  '0');
for(auto it : r) vecr.pb(it  '0');
cout << (mod + f(vecr).second  f(vecl).first) % mod << '\n'; // sum of f(x) for x in l..r = (sum of f(x) for x in 1..r)  (sum of f(x) for x in 1..l  1)
}
return 0;
}
Tester(KOTLIN)
const val MOD = 1000000007
class ModInt constructor(n: Long) {
private val v = (n % MOD + MOD) % MOD
override fun toString(): String = v.toString()
operator fun plus(other: ModInt) = ModInt(v + other.v)
operator fun minus(other: ModInt) = ModInt(v  other.v)
operator fun unaryMinus() = ModInt(v)
operator fun times(other: ModInt) = ModInt(v * other.v)
operator fun times(other: Int) = ModInt(v * (other % MOD + MOD))
operator fun times(other: Long) = ModInt(v * (other % MOD + MOD))
fun inv(): ModInt = when(v) {
1L > ModInt(1)
else > ModInt(MOD % v).inv() * (MOD  MOD / v)
}
operator fun div(other: ModInt) = this * other.inv()
operator fun div(other: Long) = this * ModInt(other).inv()
operator fun div(other: Int) = this * ModInt(other.toLong()).inv()
}
const val MAX_LEN = 100000
val POW10 = run { var pw = ModInt(10).inv(); List<ModInt>(MAX_LEN * 2 + 50) { pw *= 10; pw } }
val COEF_9_20 = ModInt(9) * ModInt(20).inv()
val COEF_99_200 = ModInt(99) * ModInt(200).inv()
fun f(s: String): ModInt {
var ret = ModInt(0)
val l = s.length
for(i in 0 until l) {
if(i == 0  s[i] != s[i1]) {
ret += POW10[l  i  1] * (s[i].toInt()  48)
}
}
return ret
}
fun g(s: String): ModInt {
var ret = ModInt(0)
val l = s.length
for(i in 1 until l) {
if(i == 0  s[i] != s[i1]) {
ret += POW10[l  i  1] * (s[i].toInt()  48)
}
}
return ret
}
val tb0 = List<ModInt>(MAX_LEN+1) { len > if(len >= 1) POW10[len * 2] * 99 / 200  POW10[len] * 9 / 20 else ModInt(0) }
val tbs = List<ModInt>(MAX_LEN+1) { len > if(len >= 1) POW10[2*(len1)] else ModInt(0) }
fun solve(s: String): ModInt {
var ret = ModInt(0)
var pref = ModInt(0)
for(i in 0 until s.length) {
for(c in 0 until s[i]  '0') {
// tb[leni1][c]
ret += pref * POW10[s.length  i  1]
if(i == 0  s[i1]  '0' != c) {
ret += (POW10[s.length  i  1] * c) * POW10[s.length  i  1]
}
ret += tb0[s.length  i  1] + tbs[s.length  i  1] * c
}
if(i == 0  s[i] != s[i1]) {
pref += POW10[s.length  i  1] * (s[i]  '0')
}
}
ret += pref
return ret
}
fun main(args: Array<String>) {
val _NUM_TESTS = readLine()!!.toInt()
require(_NUM_TESTS in 1..10)
repeat(_NUM_TESTS) {
val (Lnum, L) = readLine()!!.split(" ")
val (Rnum, R) = readLine()!!.split(" ")
require(L.length in 1..100000)
require(R.length in 1..100000)
require(L.length == Lnum.toInt())
require(R.length == Rnum.toInt())
require(L.all{ it in "0123456789" })
require(R.all{ it in "0123456789" })
require(L[0] != '0')
println(solve(R)  solve(L) + f(L))
}
}
Time Complexity=O(N)
Space Complexity=O(N)
CHEF VIJJU’S CORNER
With respect to the statement below, answer the following questions
 “An alternate way to solve the question is that, simply use dp[i_{next}][D_{next}][E_{Next}] =\sum_{D=0,D \neq D_{next}}^{D=9} \sum_{E=0}^{E=1} (dp[i][D][E] + Ct(D_{next},i)* Appropriate \ power \ of \ 10 *D_{next}) where Ct(D_{next},i) is total number of valid numbers possible with digit D_{next} at index i.”
 Comment on feasibility of this solution. Is this solution Dynamic Programming?
 Highlight about how you plan to calculate Ct(D_{next},i) or argue why calculating it is difficult.
 Our final answer by dp comes out to be correct. How does dp account for it? (Hint  Previous contribution is added for every D_{next}  i.e. it is added multiple times to accommodate for increase in digit!)
Setter's Notes
We can notice that the sum of f(x) for x in L..R = (sum of f(x) for x in 1…R)  (sum of f(x) for x in 1…L1).
We can calculate sum of f(x) for x in 1..K using dp. We will denote dp[index][digit][equal\_or\_not]  the sum of f(x) up to index, such that the last digit is digit and it is still equal to K iff equal_or_not == 1. With being still equal to K, I mean the digits up to index are the same as the digits in K up to index. Also, note that here, index 1 is the leftmost digit, as opposed to the definition in the statement. We go through the digits from the most significant digit, so that we can do it lexicographically. We should also use num[index][digit][equal\_or\_not] which is the same as the dp array, but stores only the number of possible numbers that satisfy the conditions in the states. The transitions become quite straightforward .
Ending Notes
I know this editorial is slightly longer than required  it just becomes a little hard to give the intuition behind the dp you used. That being said, the point of editorial being lengthy was to make sure you people understand it, so please point out any parts which are unclear and which you feel can be improved!
Clarification on purpose of E and UL
We broke down query into 2 parts right? One for calculating answer for upto R, and then upto L1. UL is the appropriate upper bound, i.e. either R or L1 (or L  depending on your implementation) depending on our need. Basically UL is the upper bound for which we are calculating answer.
E basically tells if "After placing this digit, is my number equal to UL at indices [0,i] " or more simply, "Are all digits in range [0,i] in my current number same as that of UL".
E_{next} tells the same for (i+1) if we place the digit d there. You may refer to setter’s solution.