数位DP。
比较蛋疼的是，设a[i]表示第i位上数字，比方说a[1]<a[2]>a[3]，且a[1]==a[3]时，这两位上的数可以放在一起搞掉。
所以就在正常的f数组里多开一维，表示后面那些位组成的不增的单调栈中，包含的数字集合。
f[i][j][k][a]表示i位，首位为j，单调栈数字集合为k，最小消除数为a的数字个数。
从已知往外推好像好写一点。。
枚举f[i1][j1][k1][a1],再枚举下一个首位j
若j<j1： f[i1+1][j][ (k1%2^(j+1))|2^j ][ a1+(2^j&k1?0:1) ]+=f[i1][j1][k1][a1];
若j==j1:f[i1+1][j][k1][a1]+=f[i1][j1][k1][a1];
若j>j1: f[i1+1][j][k1+2^j][a1+1]+=f[i1][j1][k1][a1];
统计答案时，就在记录一下已确定高位的不减单调栈就行了。。。
很(jiao)显(wan)而(cai)易(fa)见(xian)的是...j那维是没用的，因为j肯定是k的最大位...所以每个k都对应着唯一的j
反正都交了。。就懒得改了>_<
#include<cstdio>
#include<iostream>
#include<cstring>
#define ll long long
using namespace std;
ll f[][][][];
int two[],one[];
int i,j,k,n,m,aa;
int s[],st[],top;
ll L,R; inline void prerun(){
register int k1,a1,j;int i1,j1,i;ll now;
for(i=one[]=two[]=;i<;i++)two[i]=two[i-]<<,one[i]=one[i-]<<|;
for(i=;i<;i++)f[][i][two[i]][i!=]=;
for(i1=;i1<;i1++)
for(j1=;j1<;j1++)for(k1=two[j1];k1<=one[j1];k1++)for(a1=;a1<=i1&&a1<=aa;a1++)
if(f[i1][j1][k1][a1]){
now=f[i1][j1][k1][a1];
f[i1+][][][a1]+=now;
for(j=;j<j1;j++)
f[i1+][j][(k1&one[j])|two[j]][a1+!(k1&two[j])]+=now;
if(j1!=)f[i1+][j1][k1][a1]+=now;
for(j=j1+;j<;j++)
f[i1+][j][k1|two[j]][a1+]+=now;
}
}
inline int calc(int k){
register int sm=,i;
for(i=;i<=top;i++)if((st[i]!=st[i-]||i==)&&st[i]>)
if(!(two[st[i]]&k))sm++;
return sm;
}
inline ll get(ll x){
if(!x)return ;
ll tmp=x,ans=;int len=;register int i,j,k;
while(tmp)s[++len]=tmp%,tmp/=;
for(i=;i<len;i++)for(j=;j<=;j++)for(k=two[j];k<=one[j];k++)
ans+=f[i][j][k][aa];
for(j=;j<s[len];j++)for(k=two[j];k<=one[j];k++)
ans+=f[len][j][k][aa];
int pre=,tmpa;st[top=]=s[len];
for(i=len-;i;i--){
if(pre>aa)break;
for(j=;j<s[i];j++)
for(k=two[j];k<=one[j];k++)
if((tmpa=aa-pre-calc(k))>=)
ans+=f[i][j][k][tmpa];
while(top&&st[top]>s[i])pre+=(st[top]!=st[top-]||top==),top--;
st[++top]=s[i];
}
if(pre+calc()==aa)ans++;
return ans;
}
int main(){
scanf("%lld%lld%d",&L,&R,&aa);
prerun();
printf("%lld\n",get(R)-get(L-));
return ;
}