题意：求区间[l,r]内有多少个数符合，这个数的任意的相邻k位数（digits），这k个数都两两不相等
l,r范围是1~1e18,k是2~5
思路：数位DP，因为K<=5，我们最多需要保存下来当前位的前4位就足够了。因为dp[pos][p1][p2][p3][p4]表示，现在枚举取第pos位，pos位之前的四位分别为p1,p2,p3,p4,p4是pos的上一位。那么p1~p4的范围就是0~9，但是因为总位数小于当前数字的位数的数也要进行枚举，需要一个数字来区分它是前导0还是在中间时为0，令p = 10是前导0，或者表示不需要储存，即最高位的前几位。那么dfs函数可以写成 dfs( int pos , int p1 , int p2 , int p3 , int p4 , bool flag ) flag表示pos位能否取到全部的数位(0~9)还是会受到前面最高位的影响只能取一部分。
对于记忆化搜索首先明确代码的dfs的定义为当前四位分别为p1,p2,p3,p4时枚举第pos位总共有多少种方法，则dp方程很容易便能想到是1、pos位之前都取的0，即p4==10，而pos位也取0，一直都是前导零。2、而当p4!=10，pos位取的i去和p判断一下有没有重复（根据k来判断需要比较几个p），所以也是可以向下统计的，然后记得记忆化就好。
而dp的定义为当前四位数为p1,p2,p3,p4是枚举pos位总共有多少种方法，这与dfs是不同的，因为对于dp 不需要考虑必须在小于当前数的范围内进行枚举，而dfs代表的方法数必须在小于当前数的范围之内，这就可以解释第38行。同时因为大多数情况下都是flag为假，随意选择记忆这种情况可以降低复杂度（这是我猜的，如果大家有别的想法可以说出来交流一下）
#include <iostream> #include <cstdio> #include <cstring> #include <math.h> #include <algorithm> #include <queue> #include <map> using namespace std; typedef long long ll; const int N = 50000+10; const int mod=1e9+7; const double en=2.718281828459; ll l,r,dp[20][11][11][11][11]; int k,dig[20]; bool cek(int u,int p1,int p2,int p3,int p4){ if(k==2) return u!=p4; if(k==3) return u!=p4&&u!=p3; if(k==4) return u!=p4&&u!=p3&&u!=p2; if(k==5) return u!=p4&&u!=p3&&u!=p2&&u!=p1; } ll dfs(int pos,int p1,int p2,int p3,int p4,int flag){ if(pos==0) return p4!=10; if(!flag&&dp[pos][p1][p2][p3][p4]!=-1) return dp[pos][p1][p2][p3][p4];//记忆化 int ed=flag?dig[pos]:9;//当前面的数取小于其位置上的数显然后面的数可以取0~9 ll ans=0; for(int i=0;i<=ed;i++){ if(i==0&&p4==10) ans+=dfs(pos-1,10,10,10,10,flag&&i==ed); else if(cek(i,p1,p2,p3,p4)) ans+=dfs(pos-1,p2,p3,p4,i,flag&&i==ed); } if(!flag) dp[pos][p1][p2][p3][p4]=ans; return ans; } ll cal(ll u){ int cnt=0; while(u>0){ dig[++cnt]=u%10; u/=10; } return dfs(cnt,10,10,10,10,1); } int main() { //freopen("in.txt", "r", stdin); while(~scanf("%lld %lld %d",&l,&r,&k)){ memset(dp,-1,sizeof(dp)); printf("%lld ",cal(r)-cal(l-1)); } return 0; }