ural 1057 Amount of Degrees

题目地址：http://vjudge.net/problem/viewProblem.action?id=18851 (hust)

题意：给出一个区间[x,y]，在区间里找出这样的数：一个数可以表示成k个不同的b进制的次方之和，求这种数的个数。

例子讲解：x=15,y=20,k=2,b=2；那么区间里第一个满足条件的数就是17，因为17=2^4+2^0,为什么不是16，因为16=2^3+2^3,两个数相同了，所以不是16而是17。另外还有两个就是18，20；（18=2^4+2^1；20=2^4+2^2.）所以[x,y]满足条件的数的个数就是3个。

解法：数位DP。集训队论文《浅谈数位类统计问题》--刘聪中有详细讲解，不过，对于我来说，DP思维还不够，学习数位DP还是根据别人博客的记忆化搜索方法来理解入门的，我比较偏向于这种方法。大牛们请谅解我这一菜鸟，我也搞不清楚数位DP的两种实现方式：记忆化搜索和递推的优势和弊端以及时间效率上的区别。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<cstdlib>
 6 #include<algorithm>
 7 #define inf 0x7fffffff
 8 #define exp 1e-10
 9 #define PI 3.141592654
10 using namespace std;
11 typedef long long LL;
12 LL digit[40];
13 LL dp[40][25][2];
14 LL x,y,k,b;
15 LL dfs(LL len,LL num,bool flag,bool fp)
16 {
17     if (!len)
18     {
19         if (num==k) return 1;
20         return 0;
21     }
22     if (!fp && dp[len][num][flag]!=-1) return dp[len][num][flag];
23     LL ret=0;
24     LL fpmax= fp ? min((LL)1,digit[len]) : 1;
25     for (LL i=0 ;i<=fpmax ;i++)
26     {
27         if (i==0) ret += dfs(len-1,num,flag && !i,fp && i==digit[len]);
28         else ret += dfs(len-1,num+1,false,fp && i==digit[len]);
29     }
30     if (!fp) return dp[len][num][flag]=ret;
31     return ret;
32 }
33 LL f(LL n)
34 {
35     LL len=0;
36     while (n)
37     {
38         digit[++len]=n%b;
39         n /= b;
40     }
41     return dfs(len,0,true,true);
42 }
43 int main()
44 {
45     while (scanf("%I64d%I64d%I64d%I64d",&x,&y,&k,&b)!=EOF)
46     {
47         memset(dp,-1,sizeof(dp));
48         if (y<x) swap(x,y);
49         printf("%I64d
",f(y)-f(x-1));
50     }
51     return 0;
52 }