分析：赛场上也知道是裸的数位dp，但是无奈刷数位dp题刷的太少了，并不能写出来
一点感想：赛后补题，看了题解的map记录状态，一脸蒙逼，也是非常的不爽，然后想看别人写的，不是递归就是写的比较乱
而且我只刷过最入门的数位dp，例如不要62之类，伤不起啊
然后无奈之下，开了仿照别人题解开了dp[20][10][10][10][10]的数组（别人一般还写个上下限之类的代码，并不能看懂）
这样的数组就可以处理k等于5的情况了，数组第一维代表最高位，后四维代表从当前开始的4个数分别是多少
然后就可以dp[i][...]=dp[i-1][...]，当然要符合条件
然后我就是开始仿照“不要62"的那种裸数位dp的方式写这道题，各种统计啊，各种判断矛盾啊，最后辛苦AC
代码比较丑，因为写的比较直接，对于那种只会基础数位dp的人可能有帮助吧，好在最后效率还不错93ms（比某些递归还是快的）
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
using namespace std;
typedef long long LL;
const int N=1e3+;
const int INF=0x3f3f3f3f;
const int mod = 1e9+;
const LL ten=;
LL dp[][][][][],sum[][],L,R;
int k;
void up(int cur,int a,int b,int c,int d)
{
if(cur<=)
{
dp[cur][a][b][c][d]=;
sum[cur][a]+=dp[cur][a][b][c][d];
return;
}
for(int i=; i<; ++i)
{
if(i==d||(k>=&&i==c)||(k>=&&i==b)||(k>=&&i==a))continue;
dp[cur][a][b][c][d]+=dp[cur-][b][c][d][i];
}
sum[cur][a]+=dp[cur][a][b][c][d];
}
int bit[],cnt;
LL solve()
{
LL ret=;
for(int i=; i<cnt; ++i)
for(int j=; j<=; ++j)ret+=sum[i][j];
for(int i=cnt; i; --i)
{
int j=(i==cnt)?:;
for(; j<bit[i]; ++j)
{
int a=j;
bool f=false;
for(int p=min(i+k-,cnt); p>i; --p)if(a==bit[p])
{
f=true;
break;
}
if(f)continue;
if(i==)
{
ret+=dp[][a][][][];
continue;
}
for(int b=; b<; ++b)
{
if(b==a)continue;
if(k>=&&i+<=cnt&&b==bit[i+])continue;
if(k>=&&i+<=cnt&&b==bit[i+])continue;
if(k==&&i+<=cnt&&b==bit[i+])continue;
if(i==)
{
ret+=dp[][a][b][][];
continue;
}
for(int c=; c<; ++c)
{
if(c==b)continue;
if(k>=&&c==a)continue;
if(k>=&&i+<=cnt&&c==bit[i+])continue;
if(k==&&i+<=cnt&&c==bit[i+])continue;
if(i==)
{
ret+=dp[][a][b][c][];
continue;
}
for(int d=; d<; ++d)
{
if(!dp[i][a][b][c][d])continue;
if(k==&&i+<=cnt&&d==bit[i+])continue;
ret+=dp[i][a][b][c][d];
}
}
}
}
bool flag=false;
for(int p=min(i+k-,cnt); p>i; --p)if(bit[p]==bit[i])
{
flag=true;
break;
}
if(flag)break;
}
return ret;
}
int main()
{
while(~scanf("%I64d%I64d%d",&L,&R,&k))
{
memset(dp,,sizeof(dp));
memset(sum,,sizeof(sum));
++R;
cnt=;
while(R)bit[++cnt]=R%ten,R/=ten;
for(int i=; i<=cnt; ++i)
{
for(int a=; a<; ++a)
{
if(i==)
{
up(,a,,,);
continue;
}
for(int b=; b<; ++b)
{
if(b==a)continue;
if(i==)
{
up(,a,b,,);
continue;
}
for(int c=; c<; ++c)
{
if(c==b||(k>=&&c==a))continue;
if(i==)
{
up(,a,b,c,);
continue;
}
for(int d=; d<; ++d)
{
if(d==c||(k>=&&d==b)||(k>=&&d==a))continue;
up(i,a,b,c,d);
}
}
}
}
}
LL tmp=solve();
cnt=;
while(L)bit[++cnt]=L%ten,L/=ten;
printf("%I64d\n",tmp-solve());
}
return ;
}