求区间[0,N]中有多少个数满足以下条件：
任意K连续数位都是由不相同数字组成的；如数字23653(K=3)，其所有K连续数位有{236, 365, 653}，都是不存在相同数位的，既满足条件。
DP[pos][s] 表示考虑到pos数位时，以s作为最高K位的满足条件的数的个数；状态转移时只要保证新的数位与s的后K-1个数位不同即可。这里记忆化搜索的状态转移过程其实我并没有理解得很透彻，与直接递推状态的方式还是有比较大的区别，还是没有掌握到其本质。
处理s需要特别得技巧，因为需要避免将001这种数位视作合法状态，所以在最高位保留一个1，使其变成1001，这样中间重复的0就可以被检查出来；处理s的溢出位时，直接将超出K-1位的数位保留成1即可。
参考的题解：http://blog.csdn.net/ChallengerRumble/article/details/52103411
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
int bit[30];
long long dp[30][20100];
int mod;
bool ok(int p, int x){
//除最高位以外,不能有数位等于x
while(p/10){
if (p%10==x) return false;
p /= 10;
}
return true;
}
long long dfs(int isTop, int pos, int notZero, int pre){
if (pos == - 1) return 1;
while(pre-mod/10 > mod/10) pre -= mod/10;
//这行使得pre保持前K-1的状态,并且在最高位留一个1
if (!isTop&&dp[pos][pre] != -1) return dp[pos][pre];
int lastBit = isTop ? bit[pos] : 9;
long long ans = 0;
for (int i=0;i<=lastBit;i++){
if (!ok(pre,i)) continue;
if (!notZero&&i==0) ans += dfs(isTop&&i==lastBit, pos-1, notZero, pre);
else ans += dfs(isTop&&i==lastBit, pos-1, notZero+1, pre*10+i);
}
if (!isTop) dp[pos][pre] = ans;
return ans;
}
long long calc(long long n){
if (!n) return 1;
int cnt = 0;
while(n){
bit[cnt++] = n%10;
n /= 10;
}
memset(dp,-1,sizeof(dp));
return dfs(1, cnt-1, 0, 1);
}
int main(){
long long L,R;
int K;
while(~scanf("%I64d%I64d%d",&L,&R,&K)){
mod = 1;
for (int i=0;i<K;i++) mod *= 10;
printf("%I64d\n", calc(R)-calc(L-1));
}
return 0;
}
