(爆搜+数位dp)

题意:

定义一种inedible tail为一个数把每一位数字按不降的顺序排列后，去掉前导0组成的序列

比如57040 组成的就是457 54组成就是45 45组成的也是45

问区间\([L,R]\)内有多少种inedible tail

题解: 直接数位dp做，需要存状态，太大处理不了。

这个问题等价于\(x0+x1+x2+...x9=18\)的非负整数解

组合数学 插空法 \(18+9个1,选9个插空，其余变1就是解,C(18+9,9) \approx 4*10^{6}\)

所以可以暴力枚举出所有方案,然后快速判断这种方案在\([L,R]\)内是否合法

用类似数位dp的思想，用上下界来枚举每一位能取的数字，到到达某一位时即不在上界也不在下界，说明后面的数字可以随便取，那么一定取得出这种方案

由于只有在上界或者下界的时候递归才会继续往下走，所以最多走18次，线性复杂度判断

#include
    
     #define LL long long#define P pair
     
      #define ls(i) seg[i].lc#define rs(i) seg[i].rc#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define ls rt<<1#define rs (rt<<1|1)using namespace std;int read(){    int x = 0;    char c = getchar();    while(c < '0' || c > '9') c = getchar();    while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();    return x;}int pos,ans;int a[20],b[20];int cnt[10];///数字为i的个数bool is(int pos,bool Lbound,bool Rbound){    if(pos == 0) return true;    if(!Lbound && !Rbound) return true;///不是上下界,后面的数字可以任意取一定存在合法的情况    int l = Lbound?a[pos]:0;    int r = Rbound?b[pos]:9;    if(l > r) return false;    for(int i = l;i <= r;i++){///枚举每一位能取的数字        if(cnt[i]){            cnt[i]--;            if(is(pos - 1,Lbound && i == l, Rbound && i == r)){                cnt[i]++;                return true;            }            cnt[i]++;        }    }    return false;}void dfs(int cur,int total){    if(cur == 9){        cnt[cur] = total;        ans += is(pos,1,1);        return ;    }    for(int i = 0;i <= total;i++){        cnt[cur] = i;        dfs(cur + 1, total - i);    }}int digit(int *d,LL x){    int pos = 0;    while(x){        d[++pos] = x % 10;        x /= 10;    }    return pos;}int main(){    LL L,R;    cin>>L>>R;    pos = digit(a,L);    pos = digit(b,R);    ans = 0;    dfs(0,pos);///暴力枚举所有的组合    cout<
      
       <