分析：赛场上也知道是裸的数位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+5; const int INF=0x3f3f3f3f; const int mod = 1e9+7; const LL ten=10; LL dp[20][11][11][11][11],sum[20][10],L,R; int k; void up(int cur,int a,int b,int c,int d) { if(cur<=4) { dp[cur][a][b][c][d]=1; sum[cur][a]+=dp[cur][a][b][c][d]; return; } for(int i=0; i<10; ++i) { if(i==d||(k>=3&&i==c)||(k>=4&&i==b)||(k>=5&&i==a))continue; dp[cur][a][b][c][d]+=dp[cur-1][b][c][d][i]; } sum[cur][a]+=dp[cur][a][b][c][d]; } int bit[25],cnt; LL solve() { LL ret=0; for(int i=1; i<cnt; ++i) for(int j=1; j<=9; ++j)ret+=sum[i][j]; for(int i=cnt; i; --i) { int j=(i==cnt)?1:0; for(; j<bit[i]; ++j) { int a=j; bool f=false; for(int p=min(i+k-1,cnt); p>i; --p)if(a==bit[p]) { f=true; break; } if(f)continue; if(i==1) { ret+=dp[1][a][10][10][10]; continue; } for(int b=0; b<10; ++b) { if(b==a)continue; if(k>=3&&i+1<=cnt&&b==bit[i+1])continue; if(k>=4&&i+2<=cnt&&b==bit[i+2])continue; if(k==5&&i+3<=cnt&&b==bit[i+3])continue; if(i==2) { ret+=dp[2][a][b][10][10]; continue; } for(int c=0; c<10; ++c) { if(c==b)continue; if(k>=3&&c==a)continue; if(k>=4&&i+1<=cnt&&c==bit[i+1])continue; if(k==5&&i+2<=cnt&&c==bit[i+2])continue; if(i==3) { ret+=dp[3][a][b][c][10]; continue; } for(int d=0; d<10; ++d) { if(!dp[i][a][b][c][d])continue; if(k==5&&i+1<=cnt&&d==bit[i+1])continue; ret+=dp[i][a][b][c][d]; } } } } bool flag=false; for(int p=min(i+k-1,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,0,sizeof(dp)); memset(sum,0,sizeof(sum)); ++R; cnt=0; while(R)bit[++cnt]=R%ten,R/=ten; for(int i=1; i<=cnt; ++i) { for(int a=0; a<10; ++a) { if(i==1) { up(1,a,10,10,10); continue; } for(int b=0; b<10; ++b) { if(b==a)continue; if(i==2) { up(2,a,b,10,10); continue; } for(int c=0; c<10; ++c) { if(c==b||(k>=3&&c==a))continue; if(i==3) { up(3,a,b,c,10); continue; } for(int d=0; d<10; ++d) { if(d==c||(k>=3&&d==b)||(k>=4&&d==a))continue; up(i,a,b,c,d); } } } } } LL tmp=solve(); cnt=0; while(L)bit[++cnt]=L%ten,L/=ten; printf("%I64d ",tmp-solve()); } return 0; }