概要

\(1\) から \(N\) までの各整数について、その十進表記の隣接桁の差の絶対値の合計（基本スコア \(B\)）を求め、数字に \(0\) が含まれていれば \(2B\)、含まれていなければ \(B\) をスコアとし、全スコアの総和を \(10^9+7\) で割った余りを求める問題です。\(N\) が最大 \(10^{18}\) と非常に大きいため、桁DPを用います。

考察

素朴なアプローチの限界

\(N\) が最大 \(10^{18}\) なので、\(1\) から \(N\) まで一つずつスコアを計算すると \(O(N)\) かかり、到底間に合いません。

スコアの分解

各数のスコアは \(m \times B\) です。\(m\) は \(0\) を含むなら \(2\)、含まないなら \(1\) なので：

\[\text{score} = B \cdot (1 + [\text{0を含む}])\]

したがって全体の総和は：

\[\text{Total} = \sum_{\text{all}} B + \sum_{\text{0を含む}} B\]

つまり「全数の \(B\) の合計」と「\(0\) を含む数だけの \(B\) の合計」の2つを求めればよいです。

桁DPへの帰着

\(1\) から \(N\) までの全整数に対する集約は、桁DP（digit DP）の典型的な適用場面です。\(N\) の十進表記の桁数を \(L\) とすると、上位桁から1桁ずつ決めていき、\(N\) 以下であるという制約（tight 制約）を管理します。

状態設計のポイント

\(B = \sum |d_i - d_{i+1}|\) は桁ごとに加算されるため、DP遷移時に「前の桁の数字」がわかれば差分 \(|d_{\text{prev}} - d_{\text{cur}}|\) を計算できます。ただし \(B\) の値自体を状態に含めると状態数が爆発するので、\(B\) の合計値を集約して持つのがコツです。

アルゴリズム

上位桁から順に数字を確定していく桁DPを行います。各状態に対して4つの値を返します。

状態: (pos, prev, has_zero, tight, started) - pos: 現在見ている桁位置（\(0\) ～ \(L-1\)） - prev: 直前に確定した数字（\(0\)～\(9\)、未確定なら \(-1\)） - has_zero: これまでに数字 \(0\) が現れたか - tight: 上位桁がすべて \(N\) と一致しており、この桁に上限があるか - started: 有効な数字（先頭の \(0\) でない数字）が始まったか

返り値: (count, sumB, countZ, sumBZ) - count: この状態から完成する数の個数 - sumB: それらの数の \(B\) の総和 - countZ: \(0\) を含む数の個数 - sumBZ: \(0\) を含む数の \(B\) の総和

遷移: 桁 \(d\) を選んだとき、差分 \(\delta = |prev - d|\) が \(B\) に加算されます。下位の桁から返ってきた (c, sb, cz, sbz) に対し：

• sumB への寄与: \(sb + \delta \times c\)（\(c\) 個の数それぞれに \(\delta\) が加わる）
• sumBZ への寄与: \(sbz + \delta \times cz\)（\(0\) を含む \(cz\) 個の数それぞれに \(\delta\) が加わる）

最終的な答えは \(\text{sumB} + \text{sumBZ}\) です。

具体例: \(N = 10\) のとき、\(1\)～\(9\) は1桁で \(B=0\)。\(10\) は \(|1-0|=1\), \(0\)を含むので \(2 \times 1 = 2\)。総和は \(2\)。

計算量

• 時間計算量: \(O(L \times 10 \times 2 \times 2 \times 2 \times 10) = O(L \times 800)\)（\(L\) は \(N\) の桁数で最大 \(19\)、各状態で \(0\)～\(9\) の \(10\) 通りを試す）
  • 状態数は約 \(19 \times 11 \times 2 \times 2 \times 2 = 1672\) 程度、各状態で \(10\) 分岐なので全体で約 \(16720\) 回の遷移
• 空間計算量: \(O(L \times 10 \times 2 \times 2 \times 2)\)（メモ化テーブルのサイズ）

実装のポイント

• 先頭のゼロの扱い: started フラグで管理し、先頭のゼロは「数字の一部」とみなさない（has_zero を False のまま、prev も未確定のまま）。

• \(B\) の合計を状態に含めない: \(B\) そのものではなく、個数 × 差分 で合計への寄与を計算することで状態爆発を防ぐ。

• \(0\) を含む数の \(B\) の合計を別管理: countZ と sumBZ を持つことで、スコアの倍率 \(m\) の影響を正しく計算できる。

• MOD 演算: 加算のたびに \(10^9+7\) で余りを取る。

  ソースコード

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()

---

この解説は claude4.6opus-thinking によって生成されました。