求區(qū)間[0,N]中有多少個(gè)數(shù)滿足以下條件：
任意K連續(xù)數(shù)位都是由不相同數(shù)字組成的沪伙；如數(shù)字23653(K=3)胧华，其所有K連續(xù)數(shù)位有{236, 365, 653}裁奇，都是不存在相同數(shù)位的也祠，既滿足條件。
DP[pos][s] 表示考慮到pos數(shù)位時(shí)琅束，以s作為最高K位的滿足條件的數(shù)的個(gè)數(shù)；狀態(tài)轉(zhuǎn)移時(shí)只要保證新的數(shù)位與s的后K-1個(gè)數(shù)位不同即可算谈。這里記憶化搜索的狀態(tài)轉(zhuǎn)移過(guò)程其實(shí)我并沒(méi)有理解得很透徹涩禀，與直接遞推狀態(tài)的方式還是有比較大的區(qū)別，還是沒(méi)有掌握到其本質(zhì)然眼。
處理s需要特別得技巧艾船，因?yàn)樾枰苊鈱?01這種數(shù)位視作合法狀態(tài)，所以在最高位保留一個(gè)1罪治，使其變成1001丽声，這樣中間重復(fù)的0就可以被檢查出來(lái)；處理s的溢出位時(shí)觉义，直接將超出K-1位的數(shù)位保留成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){
//除最高位以外,不能有數(shù)位等于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的狀態(tài),并且在最高位留一個(gè)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;
}
