题解：P11557 [ROIR 2016 Day 2] 有趣数字

简单的数位 dp。

发现 L \leq R \leq 10^{100}，想到数位 dp。考虑用记忆化搜索实现，我们需要记录三个变量：当前遍历到的位置 p（从高位到低位），之前使用的最大数字 x 和是否顶着上限 flag。显然若 p 大于数字位数说明已经成功遍历完，返回 1；否则枚举所有第 p 位上可能的数字并继续递归。具体实现可参照代码。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll mod=1e9+7;
const int L=105;

string s,l,r;
ll f[L][10][2];
int ln;
ll solve(int p,int x,int flag) {
    if(p>=ln) return 1;
    if(~f[p][x][flag]) return f[p][x][flag];
    int lim=flag?(s[p]-'0'):9;
    f[p][x][flag]=0;
    for(int i=x;i<=lim;i++) (f[p][x][flag]+=solve(p+1,i,flag&&(i==lim)))%=mod;
    return f[p][x][flag];
}

int main() {
    cin>>l>>r,s=r,ln=s.size();
    memset(f,-1,sizeof(f));
    ll ans=solve(0,0,1);
    memset(f,-1,sizeof(f));
    s=l,ln=s.size(),ans-=solve(0,0,1)-1;
    for(int i=0;i<s.size()-1;i++)
        if(s[i]>s[i+1]) {
            ans--; break ;
        }
    ans=(ans%mod+mod)%mod;
    cout<<ans<<endl;
    return 0;
}