概要

正の整数の各桁の隣接差からなる「段差列」が単調非減少であるものを数える問題です。\(L\) 以上 \(R\) 以下にそのような数がいくつあるかを、桁DPを用いて求めます。

考察

重要な気づき

• \(R\) は最大 \(10^{5000}\) にもなりうるため、1つずつ数を調べることは不可能です。
• 「\(L\) 以上 \(R\) 以下の条件を満たす数の個数」は、\(f(N) = \) 「\(1\) 以上 \(N\) 以下の条件を満たす数の個数」とすると、\(f(R) - f(L-1)\) で求められます。
• \(f(N)\) は桁DP（Digit DP）で効率的に計算できます。

なぜ桁DPが有効か

スムーズな山道かどうかの判定に必要な情報は： - 直前の桁の数字（次の差を計算するため） - 直前の段差 \(e_{i-1}\)（単調非減少条件 \(e_{i-1} \leq e_i\) の検証のため）

これらはどちらも \(0\)〜\(9\) の範囲に収まるため、状態数が非常に少なく、桁DP の状態として管理できます。

アルゴリズム

桁DP の状態

各桁を上位から順に決めていき、以下の状態を管理します：

状態要素	値の範囲	説明
last_d	\(0\)〜\(9\) または「なし」	直前に置いた桁の数字
last_e	\(0\)〜\(9\) または「なし」	直前の段差（2桁目以降で発生）
tight	\(0\) or \(1\)	上界 \(N\) にまだ張り付いているか
started	\(0\) or \(1\)	非ゼロの桁を置いたか（先頭ゼロ処理）

遷移

位置 pos で数字 \(d\) を置くとき：

1. まだ数が始まっていない (\(started = 0\)) かつ \(d = 0\)：先頭のゼロとして無視し、状態を変えずに次へ。
2. 最初の非ゼロ桁：\(last\_d = d\) とし、段差はまだ「なし」。
3. 2桁目：新しい段差 \(e_{new} = |last\_d - d|\) を計算し、\(last\_e = e_{new}\) に設定。
4. 3桁目以降：\(e_{new} = |last\_d - d|\) を計算し、\(e_{new} \geq last\_e\) のときのみ遷移可能。

範囲の処理

\[\text{答え} = f(R) - f(L-1) \pmod{10^9 + 7}\]

\(L - 1\) は文字列上で繰り下がり処理を行って計算します。

具体例

\(N = 1234\) の場合の桁DPを考えます。\(tight = 1\) の状態では各桁が \(N\) の対応する桁以下に制限されます。例えば1桁目で \(d = 1\) を選び \(tight = 1\) のまま進む場合、2桁目は \(0\)〜\(2\) に制限されます。\(tight = 0\) になれば以降は自由に \(0\)〜\(9\) を選べます。

計算量

状態数を見積もります： - last_d: \(11\) 通り（\(0\)〜\(9\) + なし） - last_e: \(11\) 通り（\(0\)〜\(9\) + なし） - tight: \(2\) 通り - started: \(2\) 通り

各位置での状態数は最大 \(11 \times 11 \times 2 \times 2 = 484\)、各状態から最大 \(10\) 通りの遷移があります。

• 時間計算量: \(O(N \times 484 \times 10) = O(N)\)（\(N\) は桁数、最大 \(5000\)）
• 空間計算量: \(O(484) = O(1)\)（各位置で辞書を使い、前の位置の状態のみ保持）

実装のポイント

• 先頭ゼロの処理：例えば3桁の上界でDPするとき、1桁や2桁の数も正しく数えるために started フラグが必要です。

• \(L - 1\) の計算：多倍長整数を文字列で扱うため、繰り下がりを手動で処理します。\(L = 1\) のとき \(L - 1 = 0\) となり、\(f(0) = 0\) として処理します。

• 辞書ベースのDP：到達可能な状態のみを保持するため、実際には484通りすべてが現れるわけではなく効率的です。

• MOD演算：桁数が大きいため個数も巨大になりうるので、各遷移で \(10^9 + 7\) の剰余を取ります。

  ソースコード

import sys
from functools import lru_cache

def solve():
    MOD = 10**9 + 7
    input_data = sys.stdin.read().split()
    L = input_data[0]
    R = input_data[1]
    
    # Count smooth numbers in [1, N] for a given string N
    # We use digit DP
    # State: position, last_digit, last_diff (the previous e value), tight, started
    # last_diff ranges from 0 to 9, we use -1 to mean "no previous diff yet"
    
    def count_smooth(N_str):
        """Count smooth numbers in [1, N_str]"""
        n = len(N_str)
        digits = [int(c) for c in N_str]
        
        # dp with memoization
        # pos: current position (0..n-1)
        # last_d: last digit placed (0-9), -1 if not started
        # last_e: last diff value (0-9), -1 if no diff yet (0 or 1 digits placed)
        # tight: whether we're still bounded by N
        # started: whether we've placed a nonzero digit yet
        
        # We'll use iterative DP with dictionary or array
        # States: (pos, last_d, last_e, tight, started)
        # last_d: 0-9 or -1 (use 10 for -1)
        # last_e: 0-9 or -1 (use 10 for -1)
        # tight: 0 or 1
        # started: 0 or 1
        
        # Use dictionary-based DP for efficiency
        # Current states -> count
        
        # state = (last_d, last_e, tight, started)
        # We process position by position
        
        current = {}
        # Initial state before placing any digit
        # last_d=10(none), last_e=10(none), tight=1, started=0
        current[(10, 10, 1, 0)] = 1
        
        for pos in range(n):
            nxt = {}
            for (ld, le, tight, started), cnt in current.items():
                if cnt == 0:
                    continue
                limit = digits[pos] if tight else 9
                for d in range(0, limit + 1):
                    new_tight = 1 if (tight and d == limit) else 0
                    
                    if not started and d == 0:
                        # Still haven't started
                        key = (10, 10, new_tight, 0)
                        nxt[key] = (nxt.get(key, 0) + cnt) % MOD
                    else:
                        # Placing digit d
                        if not started:
                            # First digit
                            # d >= 1
                            key = (d, 10, new_tight, 1)
                            nxt[key] = (nxt.get(key, 0) + cnt) % MOD
                        else:
                            # We have a previous digit ld
                            new_e = abs(ld - d)
                            if le == 10:
                                # No previous diff, this is the second digit
                                key = (d, new_e, new_tight, 1)
                                nxt[key] = (nxt.get(key, 0) + cnt) % MOD
                            else:
                                # Check monotone non-decreasing: new_e >= le
                                if new_e >= le:
                                    key = (d, new_e, new_tight, 1)
                                    nxt[key] = (nxt.get(key, 0) + cnt) % MOD
                                # else: skip, not smooth
            current = nxt
        
        # Sum all states that have started
        result = 0
        for (ld, le, tight, started), cnt in current.items():
            if started:
                result = (result + cnt) % MOD
        
        return result
    
    def subtract_one(s):
        """Return string representation of int(s) - 1, assuming s >= 1"""
        digits = list(s)
        i = len(digits) - 1
        while i >= 0 and digits[i] == '0':
            digits[i] = '9'
            i -= 1
        # digits[i] is nonzero
        digits[i] = str(int(digits[i]) - 1)
        # Remove leading zeros
        result = ''.join(digits).lstrip('0')
        if result == '':
            result = '0'
        return result
    
    # Answer = count_smooth(R) - count_smooth(L-1)
    L_minus_1 = subtract_one(L)
    
    ans_R = count_smooth(R)
    if L_minus_1 == '0':
        ans_L = 0
    else:
        ans_L = count_smooth(L_minus_1)
    
    print((ans_R - ans_L) % MOD)

solve()

---

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