Overview

We consider each integer from \(1\) to \(N\) as a “sequence of digits (elevation sequence)” and compute the sum of adjacent digit differences \(B=\sum |d_i-d_{i+1}|\). However, numbers containing the digit \(0\) have their score doubled to \(2B\), and we need to find the total sum modulo \(10^9+7\).

Analysis

• Since \(N \le 10^{18}\), naively enumerating all numbers from \(1\) to \(N\) and computing digit differences would be \(O(N)\), which is far too slow.
• What we want is the total sum of “sums of adjacent differences over digit sequences,” which can typically be handled with Digit DP.
• Furthermore, the multiplier \(m\) condition (whether the number contains the digit \(0\)) can be handled simultaneously by including “has the number contained 0” in the DP state.

Here is an important decomposition:

• Let \(S_{\text{all}}=\sum B\) be the total of the base scores of all numbers.
• Let \(S_{\text{zero}}=\sum_{(\text{contains 0})} B\) be the total of the base scores of only those numbers containing 0.

Then the final answer is: - Numbers not containing 0: score is \(B\) - Numbers containing 0: score is \(2B = B + B\)

So: $\( \sum (mB)=S_{\text{all}} + S_{\text{zero}} \)$

Therefore, in the DP we accumulate the “sum of base scores \(B\),” and at the end we compute \(S_{\text{all}}+S_{\text{zero}}\).

Also, to handle \(1\) through \(N\), we perform DP on digit sequences of length \(L=\text{len}(N)\) allowing leading zeros (e.g., if \(N=345\), we represent numbers as 001 through 345), and we include a state “non-zero digit hasn’t started yet (started=0)” to exclude the number 0.

Algorithm

Let \(a_0,a_1,\dots,a_{L-1}\) be the digits of \(N\) from the most significant digit (scanning left to right).

DP States

dpC[tight][started][has0][last]: the count of numbers reaching this state
dpS[tight][started][has0][last]: the sum of base scores \(B\) of numbers reaching this state

• pos (loop variable): current digit position (from the left)
• tight: whether all digits so far match \(N\) and the next digit is restricted (1: restricted, 0: free)
• started: whether a non-zero leading digit has already been placed (1: number has started, 0: still in leading zeros)
• has0: whether the digit sequence after starting contains a 0 (1: contains 0)
• last: the previously placed digit (while started=0, we use 0 as a dummy value)

Initial state is “nothing decided yet”:
dpC[1][0][0][0] = 1, dpS[...] = 0

Transitions

At position pos, we choose the next digit x.

• The upper bound maxd is a_pos if tight==1, otherwise 9
• The next tight is 1 only when tight==1 and x==a_pos

When started==0: - If x==0, the number hasn’t started yet (leading zero) - nstarted=0, add=0, nhas0=0 (since the number hasn’t started, we don’t count this 0 as “containing 0”) - If x>0, the number starts - nstarted=1, nlast=x, add=0 (no adjacent difference yet)

When started==1: - Always nstarted=1 - Add add = |last - x| to the base score - nhas0 = has0 or (x==0)

Update formulas (taking mod along the way): - Count: ndpC += dpC - Base score sum: ndpS += dpS + dpC * add

The reason for dpS + dpC * add is: - We carry over the existing sum of base scores - The new add is added to every number in this group, so its total contribution is dpC * add

Computing the Answer

After processing all digits, states with started==1 represent the numbers \(1\) through \(N\) (0 is excluded).

• \(S_{\text{all}}\): sum dpS over both has0=0 and has0=1
• \(S_{\text{zero}}\): sum dpS over only has0=1

Finally, output: $\( \text{ans} = (S_{\text{all}} + S_{\text{zero}}) \bmod (10^9+7) \)$

Complexity

With the number of digits \(L \le 19\), at each digit position the number of states is \(2 \times 2 \times 2 \times 10\), and the digit choice has at most 10 options, so:

• Time complexity: \(O(L \cdot 2 \cdot 2 \cdot 2 \cdot 10 \cdot 10) = O( L )\) (with small constants)
• Space complexity: \(O(2 \cdot 2 \cdot 2 \cdot 10)\)

Implementation Notes

• To correctly handle leading zeros, we maintain the started flag and do not add adjacent differences while started==0.

• The “contains 0” check updates has0 only for digits after the number has started (padding zeros at the front are ignored).

• What we ultimately want is not \(2B\) directly; instead, we first accumulate the sum of \(B\), then apply the multiplier via the formula \(S_{\text{all}}+S_{\text{zero}}\), which is more concise.

• Note that the transition for dpS takes the form dpS + dpC * add (a standard technique in sum-based DP).

  Source Code

import sys

MOD = 10**9 + 7

def main():
    N = int(sys.stdin.readline().strip())
    digits = list(map(int, str(N)))
    L = len(digits)

    dpC = [[[[0] * 10 for _ in range(2)] for _ in range(2)] for _ in range(2)]
    dpS = [[[[0] * 10 for _ in range(2)] for _ in range(2)] for _ in range(2)]
    dpC[1][0][0][0] = 1

    for pos in range(L):
        lim_digit = digits[pos]
        ndpC = [[[[0] * 10 for _ in range(2)] for _ in range(2)] for _ in range(2)]
        ndpS = [[[[0] * 10 for _ in range(2)] for _ in range(2)] for _ in range(2)]

        for tight in range(2):
            maxd = lim_digit if tight else 9
            for started in range(2):
                for has0 in range(2):
                    for last in range(10):
                        c = dpC[tight][started][has0][last]
                        if c == 0:
                            continue
                        ssum = dpS[tight][started][has0][last]
                        for x in range(maxd + 1):
                            ntight = 1 if (tight and x == lim_digit) else 0
                            if started == 0:
                                if x == 0:
                                    nstarted, nlast, nhas0, add = 0, 0, 0, 0
                                else:
                                    nstarted, nlast, nhas0, add = 1, x, 0, 0
                            else:
                                nstarted, nlast = 1, x
                                nhas0 = has0 or (x == 0)
                                add = abs(last - x)

                            ndpC[ntight][nstarted][nhas0][nlast] = (ndpC[ntight][nstarted][nhas0][nlast] + c) % MOD
                            ndpS[ntight][nstarted][nhas0][nlast] = (ndpS[ntight][nstarted][nhas0][nlast] + ssum + c * add) % MOD

        dpC, dpS = ndpC, ndpS

    S_all = 0
    S_zero = 0
    for tight in range(2):
        for last in range(10):
            S_all = (S_all + dpS[tight][1][0][last] + dpS[tight][1][1][last]) % MOD
            S_zero = (S_zero + dpS[tight][1][1][last]) % MOD

    ans = (S_all + S_zero) % MOD
    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.