Segment Sum
Contest: Educational Codeforces Round 53 (Rated for Div. 2)
Difficulty rating: 2300
Tags: bitmasks, combinatorics, dp, math

You are given two integers $$$l$$$ and $$$r$$$ ($$$l \le r$$$). Your task is to calculate the sum of numbers from $$$l$$$ to $$$r$$$ (including $$$l$$$ and $$$r$$$) such that each number contains at most $$$k$$$ different digits, and print this sum modulo $$$998244353$$$.

For example, if $$$k = 1$$$ then you have to calculate all numbers from $$$l$$$ to $$$r$$$ such that each number is formed using only one digit. For $$$l = 10, r = 50$$$ the answer is $$$11 + 22 + 33 + 44 = 110$$$.

Input format:
The only line of the input contains three integers $$$l$$$, $$$r$$$ and $$$k$$$ ($$$1 \le l \le r < 10^{18}, 1 \le k \le 10$$$) — the borders of the segment and the maximum number of different digits.

Output format:
Print one integer — the sum of numbers from $$$l$$$ to $$$r$$$ such that each number contains at most $$$k$$$ different digits, modulo $$$998244353$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
For the first example the answer is just the sum of numbers from $$$l$$$ to $$$r$$$ which equals to $$$\frac{50 \cdot 51}{2} - \frac{9 \cdot 10}{2} = 1230$$$. This example also explained in the problem statement but for $$$k = 1$$$.

For the second example the answer is just the sum of numbers from $$$l$$$ to $$$r$$$ which equals to $$$\frac{2345 \cdot 2346}{2} = 2750685$$$.

For the third example the answer is $$$101 + 110 + 111 + 112 + 113 + 114 + 115 + 116 + 117 + 118 + 119 + 121 + 122 + 131 + 133 + 141 + 144 + 151 = 2189$$$.

Example input:
10 50 2

Example output:
1230

Example input:
1 2345 10

Example output:
2750685

Editorial:
Let's calculate the answer as the sum of suitable numbers in range $$$[1; r]$$$ minus the sum of suitable numbers in range $$$[1; l - 1]$$$. Now our problem is to calculate the sum of suitable numbers in range $$$[1; n]$$$.
The main approach for this problem is digit DP. Let's calculate two dynamic programmings $$$dp_{pos, mask, f}$$$ and $$$dps_{pos, mask, f}$$$. $$$pos$$$ means that now we are at the $$$pos$$$-th digit of the number $$$n$$$ (at the digit corresponding to $$$10^{len - pos - 1}$$$, where $$$len$$$ is the decimal length of a number), $$$mask$$$ is a binary mask describing digits we already use and $$$f$$$ equals $$$1$$$ if the current prefix of number we trying to obtain is the same as the prefix of number $$$n$$$ (otherwise $$$f$$$ equals $$$0$$$).
So what means $$$dp_{pos, mask, f}$$$? It means the count of numbers (in general, not numbers but their prefixes) in range $$$[1; n]$$$ of length exactly $$$|n|$$$ without leading zeroes corresponding to this state. So what the point of this DP? Its point is helping us to calculate the main DP, $$$dps_{pos, mask, f}$$$, which means the sum of numbers (in general, not numbers but their prefixes) in range $$$[1; n]$$$ of length exactly $$$|n|$$$ without leading zeroes corresponding to this state.
How do we calculate the answer? Firstly, let $$$len$$$ be the length of $$$n$$$. Let $$$calc(n)$$$ be the function calculating the sum of numbers from $$$1$$$ to $$$n$$$ containing at most $$$k$$$ different digits. How to calculate it? Let $$$calcdp(x)$$$ be the sum of numbers from $$$1$$$ to $$$x$$$ containing at most $$$k$$$ different digits and having length exactly $$$|x|$$$. Then $$$calc(n)$$$ seems to be pretty easy: for each length $$$i$$$ from $$$1$$$ to $$$len-1$$$ add to the answer $$$calcdp(10^i - 1)$$$. And the last step is to add to the answer $$$calcdp(n)$$$.
How to calculate dynamic programmings? Initially, all states are zeroes (excluding $$$dp_{0, 0, 1}$$$, which is $$$1$$$).
Firstly, let's calculate $$$dp$$$. After calculating it we can calculate $$$dps$$$ in almost the same way. Let's iterate over all possible lengths and over all possible masks. Let the current state is $$$dp_{pos, mask, 0}$$$. Then let's iterate over next digit we will place in this number and place it. If $$$pos = 0$$$ then $$$dig = 1 \dots 9$$$ otherwise $$$dig = 0 \dots 9$$$. The transition is pretty easy: $$$dp_{pos + 1, mask | 2^{dig}, 0} += dp_{pos, mask, 0}$$$. There $$$|$$$ is the bitwise OR operation. For $$$f = 1$$$ transitions are almost the same expect the restrictions on digit we place and the state we update. If we now at the position $$$pos$$$ with mask $$$mask$$$ and $$$f = 1$$$ then the current digit of $$$n$$$ is $$$n_{pos}$$$. Then let's iterate over next digit: $$$dig = 1 \dots n_{pos}$$$ if $$$pos = 0$$$ otherwise $$$dig = 0 \dots n_{pos}$$$. The transition is also easy: $$$dp_{pos + 1, mask | 2^{dig}, dig = n_{pos}} += dp_{pos, mask, f}$$$.
After calculating the previous DP we can calculate $$$dps$$$. All the process is the same as in the previous dynamic programming expect the value we will add in transitions. In the previous DP this value was equal $$$dp_{pos, mask, f}$$$, in the current DP this value equals to $$$val = dps_{pos, mask, f} + dig \cdot 10^{len - pos - 1} \cdot dp_{pos, mask, f}$$$. Don't forget to calculate it modulo $$$998244353$$$!
So after calculating all the values of DPs, what is the answer for $$$calcdp(n)$$$? It is $$$\sum\limits_{mask = 0}^{2^{10} - 1} dps_{|n|, mask, 0} + dps_{|n|, mask, 1}$$$ for all masks with at most $$$k$$$ bits.
I'm pretty sure that there is another way to avoid leading zeroes in calculating these DPs but this one is very straight-forward and simple.