Overview

For each integer from \(1\) to \(N\), we compute the sum of absolute differences between adjacent digits in its decimal representation (base score \(B\)). If the number contains the digit \(0\), its score is \(2B\); otherwise, the score is \(B\). We need to find the sum of all scores modulo \(10^9+7\). Since \(N\) can be as large as \(10^{18}\), we use digit DP.

Analysis

Limitations of a Naive Approach

Since \(N\) can be up to \(10^{18}\), computing the score for each number from \(1\) to \(N\) one by one takes \(O(N)\) time, which is far too slow.

Decomposing the Score

Each number’s score is \(m \times B\), where \(m\) is \(2\) if the number contains \(0\) and \(1\) otherwise:

\[\text{score} = B \cdot (1 + [\text{contains 0}])\]

Therefore, the total sum is:

\[\text{Total} = \sum_{\text{all}} B + \sum_{\text{contains 0}} B\]

In other words, we need to compute two quantities: “the sum of \(B\) over all numbers” and “the sum of \(B\) over only the numbers containing \(0\).”

Reduction to Digit DP

Aggregating over all integers from \(1\) to \(N\) is a classic application of digit DP. Let \(L\) be the number of digits in the decimal representation of \(N\). We determine digits one by one from the most significant digit, managing the constraint that the number must be at most \(N\) (the tight constraint).

Key Points of State Design

Since \(B = \sum |d_i - d_{i+1}|\) is accumulated digit by digit, we can compute the difference \(|d_{\text{prev}} - d_{\text{cur}}|\) during DP transitions as long as we know the previous digit. However, including the value of \(B\) itself in the state would cause a state explosion, so the key technique is to aggregate the sum of \(B\) values.

Algorithm

We perform digit DP, determining digits from the most significant position. Each state returns four values.

State: (pos, prev, has_zero, tight, started) - pos: current digit position (\(0\) to \(L-1\)) - prev: the most recently determined digit (\(0\) to \(9\); \(-1\) if undetermined) - has_zero: whether the digit \(0\) has appeared so far - tight: whether all higher digits match \(N\), imposing an upper bound on this digit - started: whether a significant digit (a non-zero leading digit) has been placed

Return values: (count, sumB, countZ, sumBZ) - count: the number of numbers completed from this state - sumB: the sum of \(B\) over those numbers - countZ: the count of numbers containing \(0\) - sumBZ: the sum of \(B\) over numbers containing \(0\)

Transitions: When choosing digit \(d\), the difference \(\delta = |prev - d|\) is added to \(B\). Given (c, sb, cz, sbz) returned from the lower digits:

• Contribution to sumB: \(sb + \delta \times c\) (each of the \(c\) numbers gains an additional \(\delta\))
• Contribution to sumBZ: \(sbz + \delta \times cz\) (each of the \(cz\) numbers containing \(0\) gains an additional \(\delta\))

The final answer is \(\text{sumB} + \text{sumBZ}\).

Concrete example: When \(N = 10\), numbers \(1\) through \(9\) are single-digit with \(B=0\). For \(10\), \(|1-0|=1\) and it contains \(0\), so its score is \(2 \times 1 = 2\). The total sum is \(2\).

Complexity

• Time complexity: \(O(L \times 10 \times 2 \times 2 \times 2 \times 10) = O(L \times 800)\) (\(L\) is the number of digits of \(N\), at most \(19\); each state tries \(10\) choices from \(0\) to \(9\))
  • The number of states is approximately \(19 \times 11 \times 2 \times 2 \times 2 = 1672\), and with \(10\) branches per state, the total number of transitions is about \(16720\)
• Space complexity: \(O(L \times 10 \times 2 \times 2 \times 2)\) (size of the memoization table)

Implementation Notes

• Handling leading zeros: Managed with the started flag. Leading zeros are not treated as “part of the number” (has_zero remains False and prev stays undetermined).

• Not including the sum of \(B\) in the state: Instead of tracking \(B\) itself, we compute contributions to the total as count × difference, preventing state explosion.

• Separately tracking the sum of \(B\) for numbers containing \(0\): By maintaining countZ and sumBZ, we correctly account for the score multiplier \(m\).

• MOD arithmetic: Take the remainder modulo \(10^9+7\) with every addition.

  Source Code

import sys
from functools import lru_cache

def solve():
    MOD = 10**9 + 7
    N = int(input())
    
    # We need to compute sum of hiking scores for all numbers from 1 to N.
    # Hiking score for number with digits d1,...,dk:
    #   B = sum |d_i - d_{i+1}|
    #   m = 2 if any digit is 0, else 1
    #   score = m * B
    #
    # So score = B + B * [has zero] = B * (1 + [has zero])
    # Total = sum of B for all numbers + sum of B*[has zero] for all numbers
    #
    # We'll use digit DP on the digits of N.
    # 
    # State: position, previous digit, sum of |differences| so far, has_zero flag, tight flag, started flag
    # But sum of |differences| can be huge, so we can't track it directly.
    # 
    # We need to accumulate contributions. Let's think about what we need:
    # For each number, contribution = m * B where m in {1,2}, B = sum of |d_i - d_{i+1}|
    # = B + [has_zero] * B
    #
    # So total = S1 + S2 where:
    # S1 = sum over all numbers of B
    # S2 = sum over all numbers that contain digit 0, of B
    #
    # For digit DP, at each state we track:
    # - count of numbers
    # - sum of B values
    # And we do this separately for "has zero" and "no zero" variants, or track both.
    #
    # State: (pos, prev_digit, has_zero, tight, started)
    # Values: (count, sum_of_B)
    #
    # When started=False, we haven't placed a nonzero digit yet (leading zeros).
    
    digits = list(map(int, str(N)))
    L = len(digits)
    
    # Memoization with dict since lru_cache might be slow with many states
    # States: (pos, prev, has_zero, tight, started)
    # prev: 0-9 or -1 (no previous digit placed yet)
    # Returns: (count, sum_B, sum_B_with_zero)
    # sum_B = total of B values for all numbers formed
    # sum_B_with_zero = total of B values for numbers that have at least one zero digit
    
    # We'll track (count, sum_B, count_with_zero, sum_B_with_zero)
    # Then answer = sum_B + sum_B_with_zero (mod MOD)
    
    memo = {}
    
    def dp(pos, prev, has_zero, tight, started):
        # returns (count, sum_B, count_with_zero, sum_B_with_zero)
        if pos == L:
            if not started:
                return (0, 0, 0, 0)
            cz = 1 if has_zero else 0
            return (1, 0, cz, 0)
        
        key = (pos, prev, has_zero, tight, started)
        if key in memo:
            return memo[key]
        
        limit = digits[pos] if tight else 9
        
        res_count = 0
        res_sumB = 0
        res_countZ = 0
        res_sumBZ = 0
        
        for d in range(0, limit + 1):
            new_tight = tight and (d == limit)
            
            if not started and d == 0:
                # Still not started
                c, sb, cz, sbz = dp(pos + 1, -1, False, new_tight, False)
                res_count = (res_count + c) % MOD
                res_sumB = (res_sumB + sb) % MOD
                res_countZ = (res_countZ + cz) % MOD
                res_sumBZ = (res_sumBZ + sbz) % MOD
            else:
                new_started = True
                new_has_zero = has_zero or (d == 0)
                new_prev = d
                
                if started and prev != -1:
                    diff = abs(prev - d)
                else:
                    diff = 0
                
                c, sb, cz, sbz = dp(pos + 1, new_prev, new_has_zero, new_tight, new_started)
                
                # Each of the c numbers gets +diff added to their B
                res_count = (res_count + c) % MOD
                res_sumB = (res_sumB + sb + diff * c) % MOD
                res_countZ = (res_countZ + cz) % MOD
                res_sumBZ = (res_sumBZ + sbz + diff * cz) % MOD
        
        memo[key] = (res_count, res_sumB, res_countZ, res_sumBZ)
        return memo[key]
    
    count, sumB, countZ, sumBZ = dp(0, -1, False, True, False)
    
    # Total = sumB + sumBZ (since score = B * (1 + [has_zero]), and sumBZ is sum of B for those with zero)
    answer = (sumB + sumBZ) % MOD
    print(answer)

solve()

---

This editorial was generated by claude4.6opus-thinking.