概要

与えられた範囲 \([L, R]\) に含まれる正の整数のうち、隣接する桁の差（絶対値）が単調非減少である「スムーズな山道」の個数を求める問題です。\(L\) と \(R\) は最大で \(5000\) 桁という非常に大きな数であるため、桁 DP（桁を 1 つずつ決定していく動的計画法）を用いて解きます。

考察

1. 「スムーズな山道」の条件の分解

ある数 \(X\) の各桁を \(d_1, d_2, \ldots, d_k\) としたとき、隣接する桁の差を \(e_i = |d_i - d_{i+1}|\) とします。条件は \(e_1 \leq e_2 \leq \ldots \leq e_{k-1}\) です。 この条件を判定するためには、次の桁 \(d_{i+1}\) を決める際に以下の 2 つの情報が必要になります。 - 直前の桁 \(d_i\) （次の差 \(e_i = |d_i - d_{i+1}|\) を計算するため） - 直前の差 \(e_{i-1}\) （\(e_{i-1} \leq e_i\) を満たしているか確認するため）

2. 桁 DP の設計

桁数が非常に大きいため、標準的な桁 DP を適用します。 まず、範囲 \([L, R]\) の個数を求めるために、count(R) - count(L-1) もしくは count(R) - count(L) + (Lが条件を満たすか) という形で計算します。

DP の状態として、以下の値を定義します。 - dp[i][d][p] : 残り \(i\) 桁を埋める方法のうち、直前の桁が \(d\)、直前の差が \(p\) であるとき、その後の桁の並べ方が「スムーズな山道」の条件を維持するような組み合わせ数。

ここで、\(d\) は \(0 \sim 9\)、\(p\) も（差の最大値なので）\(0 \sim 9\) の範囲に収まります。

3. 効率的な遷移

dp[i][d][p] を求めるには、次の桁 \(nd\) を \(0 \sim 9\) の範囲で試します。 新しい差 \(new\_diff = |d - nd|\) が \(p \leq new\_diff\) を満たす場合、dp[i-1][nd][new\_diff] の値を加算します。 これをそのまま計算すると、遷移に \(O(10)\) かかり、全体で \(O(\text{桁数} \times 10 \times 10 \times 10)\) となります。桁数が \(5000\) なのでこれでも間に合いますが、累積和（Suffix Sum）を使うことでさらに高速化が可能です。

アルゴリズム

1. DP テーブルの事前計算

後ろの桁から順に、以下の手順で DP テーブルを埋めます。 1. ベースケース：残り \(0\) 桁のとき、どのような \((d, p)\) に対しても条件を満たして終了しているので \(1\) 通り。 2. 遷移：残り \(i\) 桁の場合 - 各 \(d, nd \in [0, 9]\) について、差 \(diff = |d - nd|\) ごとに dp[i-1][nd][diff] を集計する。 - \(p\) が大きくなるほど選べる \(nd\) が減る（\(diff \geq p\) の条件）ため、後ろから累積和をとることで、各 dp[i][d][p] を \(O(1)\) で計算する。

2. 範囲内の個数カウント関数 \(f(S)\)

文字列 \(S\) 以下の「スムーズな山道」を数えます。 - 桁数が \(S\) より小さい数: 先頭の桁 \(d \in [1, 9]\) を固定し、残りの桁を DP テーブルから参照して足します。 - 桁数が \(S\) と同じ数: 上から \(i\) 桁目まで \(S\) と一致している状態で、次の桁に \(S[i]\) より小さい数字を使う場合を数え上げます。 途中で \(S\) の接頭辞自体が条件に違反した（\(e_i < e_{i-1}\) となった）場合は、それ以降の探索を打ち切ります。

3. \(L\) の判定と最終回答

\(f(R) - f(L)\) を計算した後、\(L\) 自体が「スムーズな山道」であれば \(+1\) します。\(L\) が非常に大きいため、\(L-1\) を求めるよりもこの方法が安全です。

計算量

• 時間計算量: \(O(N \cdot D^2)\)

  • \(N\): 最大桁数 (\(5000\))
  • \(D\): 数字の種類 (\(10\))
  • DP の事前計算に \(O(N \cdot D^2)\)、クエリ処理に \(O(N \cdot D)\) かかります。全体で約 \(5 \times 10^5\) 回の操作となり、制限時間内に十分収まります。

• 空間計算量: \(O(N \cdot D^2)\)

  • DP テーブルの保持に \(5000 \times 10 \times 10\) の領域を使用します。

実装のポイント

• 大きな桁数の扱い: \(L, R\) は文字列として読み込み、一桁ずつ処理します。

• モジュロ演算: 答えが非常に大きくなるため、計算の各段階で \(10^9 + 7\) で余りをとります。

• 最初の差の扱い: 最初の 2 桁を決める際、比較対象となる「直前の差」は存在しません。これは「直前の差が \(0\) であった」とみなすことで、すべての差 \(e_1 \geq 0\) を許容するように統一的に処理できます。

  ソースコード

import sys

# The problem asks for the count of "smooth mountain paths" in the range [L, R].
# A number is a smooth mountain path if its sequence of digit differences
# |d_i - d_{i+1}| is monotonically non-decreasing.
# L and R can have up to 5000 digits.

def solve():
    # Fast I/O to read L and R
    input_data = sys.stdin.read().split()
    if len(input_data) < 2:
        return
    L_str = input_data[0]
    R_str = input_data[1]
    MOD = 10**9 + 7

    max_len = len(R_str)
    # dp[i * 100 + d * 10 + p]
    # i: number of digits remaining to be placed
    # d: the last digit that was placed
    # p: the difference between the last two digits placed
    dp = [0] * ((max_len + 1) * 100)
    
    # Base case: i = 0 (no more digits to place)
    # Any sequence that has reached this point is already smooth.
    for d in range(10):
        for p in range(10):
            dp[d * 10 + p] = 1
    
    # Precompute the DP table in O(max_len * 10 * 10)
    for i in range(1, max_len + 1):
        prev_idx = (i - 1) * 100
        curr_idx = i * 100
        for d in range(10):
            # Group by the absolute difference between d and the next digit nd
            diff_sums = [0] * 10
            for nd in range(10):
                diff = abs(d - nd)
                diff_sums[diff] = (diff_sums[diff] + dp[prev_idx + nd * 10 + diff]) % MOD
            
            # Use suffix sums to calculate dp[i][d][p] = sum_{diff >= p} diff_sums[diff]
            suffix_sum = 0
            for p in range(9, -1, -1):
                suffix_sum = (suffix_sum + diff_sums[p]) % MOD
                dp[curr_idx + d * 10 + p] = suffix_sum

    def f(S):
        """Count smooth mountain paths in the range [1, S]."""
        n = len(S)
        if n == 0:
            return 0
        S_ints = [int(c) for c in S]
        res = 0
        
        # Case 1: Numbers with fewer digits than S
        for length in range(1, n):
            # A number with 'length' digits starts with d in [1, 9]
            # and has (length - 1) more digits to be placed.
            # The first difference can be anything (>= 0).
            for d in range(1, 10):
                res = (res + dp[(length - 1) * 100 + d * 10 + 0]) % MOD
        
        # Case 2: Numbers with the same number of digits as S
        # Handle the first digit d where 1 <= d < S[0]
        for d in range(1, S_ints[0]):
            res = (res + dp[(n - 1) * 100 + d * 10 + 0]) % MOD
        
        # Prefix is fixed to S[0], now consider digits at position i > 0
        prev_diff = 0
        for i in range(1, n):
            s_prev = S_ints[i-1]
            limit = S_ints[i]
            # Try all digits d < limit at the current position i
            for d in range(limit):
                new_diff = abs(s_prev - d)
                # If i == 1, there's no previous difference to compare with.
                # If i > 1, the new difference must be >= the previous difference.
                if i == 1 or new_diff >= prev_diff:
                    res = (res + dp[(n - 1 - i) * 100 + d * 10 + new_diff]) % MOD
            
            # Now set the digit at position i to S_ints[i] and continue
            new_diff = abs(s_prev - limit)
            if i > 1 and new_diff < prev_diff:
                # The prefix itself is no longer smooth, so we stop here
                break
            prev_diff = new_diff
        else:
            # If the loop finished without breaking, the number S itself is smooth
            res = (res + 1) % MOD
            
        return res % MOD

    def is_smooth(S):
        """Check if a specific string S represents a smooth mountain path."""
        n = len(S)
        if n <= 2:
            return True
        S_ints = [int(c) for c in S]
        p_diff = abs(S_ints[0] - S_ints[1])
        for i in range(2, n):
            c_diff = abs(S_ints[i-1] - S_ints[i])
            if c_diff < p_diff:
                return False
            p_diff = c_diff
        return True

    # The result is count(R) - count(L) + 1 (if L is smooth)
    ans_r = f(R_str)
    ans_l = f(L_str)
    ans = (ans_r - ans_l + MOD) % MOD
    if is_smooth(L_str):
        ans = (ans + 1) % MOD
        
    print(ans % MOD)

if __name__ == '__main__':
    solve()

---

この解説は gemini-3-flash-thinking によって生成されました。