概要

\(1\) から \(N\) までの各整数を「桁列（標高列）」とみなし、隣接桁差の和 \(B=\sum |d_i-d_{i+1}|\) を合計します。ただし数字 \(0\) を含む数はスコアが \(2B\) になるので、その総和を \(10^9+7\) で求めます。

考察

• \(N \le 10^{18}\) なので、\(1\) から \(N\) を素直に列挙して桁差を計算すると \(O(N)\) で到底間に合いません。
• 求めたいのは「桁列に対する隣接差の和」の総和であり、これは典型的に 桁DP（Digit DP） で処理できます。
• さらに倍率 \(m\) の条件（数字 \(0\) を含むかどうか）も、DP状態に「0を含んだか」を持たせれば同時に扱えます。

ここで重要な分解があります：

• すべての数の基本スコアの総和を \(S_{\text{all}}=\sum B\)
• 0 を含む数だけの基本スコアの総和を \(S_{\text{zero}}=\sum_{(\text{0含む})} B\)

とすると、最終的な答えは - 0 を含まない数：\(B\) - 0 を含む数：\(2B = B + B\)

なので $\( \sum (mB)=S_{\text{all}} + S_{\text{zero}} \)\( となります。よって DP では「基本スコア \)B\( の総和」を集計し、最後に \)S{\text{all}}+S{\text{zero}}$ を取ればよいです。

また、\(1\) 〜 \(N\) を扱うために、長さ \(L=\text{len}(N)\) の桁列で 先頭に 0 を許した形（例：\(N=345\) なら 001〜345 のような表現）でDPし、「まだ非ゼロが始まっていない（started=0）」を状態に持って数 0 を除外します。

アルゴリズム

\(N\) を上からの桁列 \(a_0,a_1,\dots,a_{L-1}\) とします（左から走査）。

DP状態

dpC[tight][started][has0][last]：その状態に到達する 個数
dpS[tight][started][has0][last]：その状態に到達する数たちの 基本スコア \(B\) の総和

• pos（ループ変数）：今見ている桁位置（左から）
• tight：ここまでが \(N\) と一致していて次の桁が制限されるか（1:制限あり, 0:自由）
• started：すでに先頭の非ゼロ桁を置いたか（1:数が始まった, 0:まだ先頭の0の列）
• has0：開始後の桁列に 0 を含んだか（1:含む）
• last：直前に置いた桁（started=0 の間はダミーで 0 を使う）

初期状態は「まだ何も決めていない」ので
dpC[1][0][0][0] = 1, dpS[...] = 0

遷移

位置 pos で次の桁 x を選びます。

• 上限 maxd は tight==1 なら a_pos、そうでなければ 9
• 次の tight は、tight==1 かつ x==a_pos のときだけ 1

started==0 のとき： - x==0 ならまだ開始しない（leading zero） - nstarted=0, add=0, nhas0=0（数が始まっていないので 0 を「含んだ」とは数えない） - x>0 なら開始する - nstarted=1, nlast=x, add=0（隣接差はまだ発生しない）

started==1 のとき： - 必ず nstarted=1 - add = |last - x| を基本スコアに加える - nhas0 = has0 or (x==0)

更新式（mod を取りながら）： - 個数：ndpC += dpC - 基本スコア総和：ndpS += dpS + dpC * add

ここで dpS + dpC * add となるのは、 - 既に持っている基本スコアの総和に加え - 今回新たに全ての列に同じ add が増えるので、その総和は dpC * add になるためです。

答えの作り方

全桁処理後、started==1 の状態が \(1\)〜\(N\) を表します（0は除外）。

• \(S_{\text{all}}\)：has0=0 と has0=1 の両方の dpS を合計
• \(S_{\text{zero}}\)：has0=1 の dpS だけ合計

最後に $\( \text{ans} = (S_{\text{all}} + S_{\text{zero}}) \bmod (10^9+7) \)$ を出力します。

計算量

桁数 \(L \le 19\) として、各桁で状態数は \(2 \times 2 \times 2 \times 10\)、遷移の数字選択が最大 10 通りなので

• 時間計算量: \(O(L \cdot 2 \cdot 2 \cdot 2 \cdot 10 \cdot 10) = O( L )\)（定数が小さい）
• 空間計算量: \(O(2 \cdot 2 \cdot 2 \cdot 10)\)

実装のポイント

• leading zero（先頭の0） を正しく扱うために started を持ち、started==0 の間は隣接差を増やさないようにします。

• 「0 を含むか」の判定は、started 後の桁についてのみ has0 を更新します（先頭の埋め0は無視）。

• 最終的に欲しいのは \(2B\) ではなく、まず \(B\) の総和を集計し、式 \(S_{\text{all}}+S_{\text{zero}}\) で倍率分を反映するのが簡潔です。

• dpS の遷移は dpS + dpC * add の形になる点（総和DPの定石）に注意します。

  ソースコード

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

---

この解説は gpt-5.2-high によって生成されました。