思路:数位dp模板题

先跟着灵神学一下 数位dp

然后你就会了...

因为其实就是一个非常裸的数位dp。刷过哪怕一道数位dp的题，你就能够立马反应过来。

在模板的基础上做一个更改:dfs的过程中转移当前数位的最大值$mx$。递归出口返回$mx$即可。

代码

C++

#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000007;

int dp[20][15][2];

int solve(long long num) {
    if (num == 0) {
        return 0;
    }
    string s = to_string(num);
    int n = s.length();
    memset(dp, -1, sizeof(dp));
	// 以下就是灵神的数位dp模板 , 过程中转移mx就完事了
    function<int(int, int, int)> f = [&](int i, int mx, int lim) {
        if (i == n) {
            return mx;
        }
        if (dp[i][mx][lim] != -1) {
            return dp[i][mx][lim];
        }
        int up = lim ? s[i] - '0' : 9;
        int ans = 0;
        for (int j = 0; j <= up; j++) {
            ans += f(i + 1, max(mx, j), lim && (j == up));
            ans %= mod;
        }
        dp[i][mx][lim] = ans;
        return ans;
    };
    return f(0, 0, 1);
}

int main() {
    long long l, r;
    cin >> l >> r;
    int result = (solve(r) - solve(l - 1) + mod) % mod;
    cout << result << endl;
    return 0;
}

Python

mod = 10**9 + 7
def solve(num):
    if num == 0:
        return 0
    s = str(num)
    n = len(s)
	#以下就是灵神的数位dp模板 , 过程中转移mx就完事了
    dp = [[[-1 , -1] for i in range(15)] for j in range(20)]
    def f(i,mx,lim):
        if i == n:
            return mx
        if dp[i][mx][lim] != -1:
            return dp[i][mx][lim]
        up = int(s[i]) if lim else 9
        ans = 0
        for j in range(0,up+1):
            ans  += f(i+1,max(mx , j),lim and j == up)
            ans %= mod
        dp[i][mx][lim] = ans
        return ans
    return f(0,0 , True)
l , r = map(int , input().split())
print ((solve(r) - solve(l - 1) + mod) % mod)

Java

import java.util.Scanner;

public class Main {
    static final int mod = 1000000007;
    static int[][][] dp;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long l = scanner.nextLong();
        long r = scanner.nextLong();
        int result = (solve(r) - solve(l - 1) + mod) % mod;
        System.out.println(result);
    }

    public static int solve(long num) {
        if (num == 0) {
            return 0;
        }
        String s = Long.toString(num);
        int n = s.length();
        dp = new int[20][15][2];
        for (int i = 0; i < 20; i++) {
            for (int j = 0; j < 15; j++) {
                dp[i][j][0] = -1;
                dp[i][j][1] = -1;
            }
        }

        return f(0, 0, true, s, n);
    }
	// 以下就是灵神的数位dp模板 , 过程中转移mx就完事了
    public static int f(int i, int mx, boolean lim, String s, int n) {
        if (i == n) {
            return mx;
        }
        if (dp[i][mx][lim ? 1 : 0] != -1) {
            return dp[i][mx][lim ? 1 : 0];
        }
        int up = lim ? s.charAt(i) - '0' : 9;
        int ans = 0;
        for (int j = 0; j <= up; j++) {
            ans += f(i + 1, Math.max(mx, j), lim && (j == up), s, n);
            ans %= mod;
        }
        dp[i][mx][lim ? 1 : 0] = ans;
        return ans;
    }
}

题目内容

定义$f(d)$为$d$的最大数位的值 例如:

$f(1012)=max(1,0,1,2)=2$

$f(988)= max(9,8,8)=9$

由于答案可能很大，请求出$\sum_{i=x}^{y}f(i)$ 在模$10^9+7$ 意义下的取值。

输入描述

输入两个整数$x,y$。

$1 \leq x \leq y \leq 10^{18}$

输出描述

输出一个非负整数，表示答案

样例

输入输出示例仅供调试，后台判题数据一般不包含示例

输入

7 8

输出

15

说明

$\sum_{i=7}^{8}f(i)=f(7)+f(8)=15$

样例2

输入输出示例仅供调试，后台判题数据一般不包含示例

输入

2 202

输出

1236