思路：数位DP

定义$dp(i,mask,isLimit,isNum)$表示构造第$i$位及其之后的数位的合法方案数

• $mask$表示前面选过的数字集合，换句话说，第$i$位要选的数字不能出现在$mask$中
• $isLimit$表示当前是否受到了$n$的约束。若为真，则第$i$位填入的数字至多为 $s[i]$，否则可以是$9$
• $isNum$表示$i$前面是否填了数字，若为假，则当前位可以跳过（不填数字），或者要填入的数字至少为 1（不允许出现前导0）；若为真，则要填入的数字可以从 0 开始。

代码

C++

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int>PII;
#define x first
#define y second
typedef long long ll;
const int N=1E5+10,mod=1e9+7;
int f[N][10],n,res;
string s;
int dp(int i,int mask,bool is_limit,bool is_num){
    if(i==n){
        return is_num;  // is_num 为 true 表示得到了一个合法数字
    }
    if (!is_limit && is_num && f[i][mask] != -1){
        return f[i][mask];
    }
    int res=0;
    if(!is_num){  //跳过当前数位
        res=dp(i+1,mask,false,false);
    }
    int up=(is_limit)?s[i]-'0':9;// 如果前面填的数字都和 n 的一样，那么这一位至多填数字 s[i]（否则就超过 n 啦）
    for(int d=1-is_num;d<=up;d++){  //不能出现前导0
        if(d!=mask){
            res=(res+dp(i+1,d,is_limit&&d==up,true))%mod;
        }
    }
    if(!is_limit&&is_num){
        f[i][mask]=res;
    }
    return res;
}
int main() {
    cin>>s;
    n=s.size();
    memset(f,-1,sizeof f);
    cout<<dp(0,0,true,false)<<endl;
    return 0;
}

Java

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static final int N = 100000 + 10;
    static final int mod = 1000000007;
    static int[][] f = new int[N][10];
    static int n;
    static String s;

    static int dp(int i, int mask, boolean isLimit, boolean isNum) {
        if (i == n) {
            return isNum ? 1 : 0;  // isNum 为 true 表示得到了一个合法数字
        }
        if (!isLimit && isNum && f[i][mask] != -1) {
            return f[i][mask];
        }
        int res = 0;
        if (!isNum) {  //跳过当前数位
            res = dp(i + 1, mask, false, false);
        }
        int up = isLimit ? s.charAt(i) - '0' : 9; // 如果前面填的数字都和 n 的一样，那么这一位至多填数字 s[i]（否则就超过 n 啦）
        for (int d = isNum ? 0 : 1; d <= up; d++) {  //不能出现前导0
            if (d != mask) {
                res = (res + dp(i + 1, d, isLimit && d == up, true)) % mod;
            }
        }
        if (!isLimit && isNum) {
            f[i][mask] = res;
        }
        return res;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        s = scanner.nextLine();
        n = s.length();
        for (int[] row : f) {
            Arrays.fill(row, -1);
        }
        System.out.println(dp(0, 0, true, false));
    }
}

Python

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static final int N = 100000 + 10;
    static final int mod = 1000000007;
    static int[][] f = new int[N][10];
    static int n;
    static String s;

    static int dp(int i, int mask, boolean isLimit, boolean isNum) {
        if (i == n) {
            return isNum ? 1 : 0;  // isNum 为 true 表示得到了一个合法数字
        }
        if (!isLimit && isNum && f[i][mask] != -1) {
            return f[i][mask];
        }
        int res = 0;
        if (!isNum) {  //跳过当前数位
            res = dp(i + 1, mask, false, false);
        }
        int up = isLimit ? s.charAt(i) - '0' : 9; // 如果前面填的数字都和 n 的一样，那么这一位至多填数字 s[i]（否则就超过 n 啦）
        for (int d = isNum ? 0 : 1; d <= up; d++) {  //不能出现前导0
            if (d != mask) {
                res = (res + dp(i + 1, d, isLimit && d == up, true)) % mod;
            }
        }
        if (!isLimit && isNum) {
            f[i][mask] = res;
        }
        return res;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        s = scanner.nextLine();
        n = s.length();
        for (int[] row : f) {
            Arrays.fill(row, -1);
        }
        System.out.println(dp(0, 0, true, false));
    }
}

题目描述

“非常的新鲜，非常的美味”，这是我修院对美食的极大赞赏。

如何定义一道美食为美味呢，我塔子百思不得其解，我修院解释道：假设一道美食有一个美味值，当且仅当它的相邻数位都不相同。例如:114514是不美味的，但1919810则美味的很呐！

塔子有些困惑，想做更多的尝试（大悲），他想知道，美味值不大于x的美食中有多少道是美味的?

答案对$10^9+7$取模。

输入描述

一个正整数$x$, $1$ $<$ $x$ $<$ $10^{100000}$

输出描述

不大于$x$的美味的菜的数量，对$10^9+7$取模

样例

输入

15

输出

14

说明

不大于15的正整数中，只有11是不美味的

Limitation

1s, 1024KiB for each test case.