HDU 5787 K-wolf Number

题意： 找出区间中任意连续K个位置无重复数字的个数

思路；    dp i j 表示第i 位置， 前k位上的数字是多少

#include <map>
#include <set>
#include <queue>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>

using namespace std;
typedef long long ll;
ll mod;
ll dp[20][100000];
int digit[20];
int vis[20];
int save[20];
ll k,tot;
ll dfs(int len,int limit,int status,int pre,int num)
{
    if(len<0)
    {
        return 1;
    }
    if(!limit&&dp[len][status]!=-1)
        return dp[len][status];
    int last;
    if(limit) last=digit[len];
    else last=9;
    ll ans=0;
    for(int i=0;i<=last;i++)
    {
        if(vis[ i ] - len>=k)
        {
            int tmp=vis[i];
            if(pre&&(i==0))
            {}
            else
            vis[i]=len;
            int newstatus=status*10+i;
            //printf("%d  %d--",newstatus,pow(10,k));
            if(num>=k)
            {
                newstatus%=mod;
            }
            //printf("%d %d %d %d \n",status,newstatus, save[len+k],k);
            save[len]=i;
            ans+=dfs(len-1,limit&&i==last,newstatus,pre&&i==0, num+(!(pre&&i==0))   );
            vis[i]=tmp;
        }
    }
    if(!limit)
        dp[len][status] = ans;
    return ans;
}
ll solve(ll x)
{
    memset(save,0,sizeof(vis));
    memset(vis,0,sizeof(vis));
    memset(dp,-1,sizeof(dp));
        for(int i=0;i<=9;i++)
            vis[i]=100;
        tot=0;
    int cnt=0;
    while(x!=0)
    {
        digit[cnt++]=x%10;
        x/=10;
    }
    tot=cnt-1;
    return dfs( cnt-1, 1, 0 ,1 ,0) ;
}

int main()
{
    int t;
    ll l,r;
    while(scanf("%lld%lld%lld",&l,&r,&k)!=EOF)
    {
        mod=1;
        for(int i=1;i<=k;i++)
            mod*=10;
        ll ans=solve(r);
        //printf("%lld\n",solve(r));
        //printf("%lldxx\n",solve(l-1));
        printf("%lld\n",solve(r)-solve(l-1));
    }
}
/*
1 10 1
*/