求區(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;
}