1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=1e5+5;
 4 int tot,e[40];
 5 long long c[40][40]; 
 6 int l,r,k,b;
 7 template<class t>void red(t &x)
 8 {
 9     int w=1;
10     x=0;
11     char ch=getchar();
12     while(ch>'9'||ch<'0')
13     {
14         if(ch=='-')
15             w=-1;
16         ch=getchar(); 
17     }
18     while(ch>='0'&&ch<='9')
19     {
20         x=(x<<3)+(x<<1)+ch-'0';
21         ch=getchar();
22     } 
23     x*=w;
24 } 
25 void input()
26 {
27     freopen("input.txt","r",stdin);
28 }
29 void dv(int x)
30 {
31     tot=0;
32     while(x)
33     {
34         e[++tot]=x%b;
35         x/=b;
36     }
37     e[++tot]=0;
38 }
39 long long dfs(int pos,bool limit,int sum)
40 {
41     if(sum<0)
42         return 0;
43     if(pos==0)
44         return sum?0:1;
45     if(!limit&&~c[pos][sum]) 
46         return c[pos][sum];
47     int ans=0;
48     int up=limit?min(e[pos],1):1;
49     for(int i=0;i<=up;++i)
50         ans+=dfs(pos-1,limit&&(i==e[pos]),sum-i);
51     if(!limit)
52         c[pos][sum]=ans;
53     return ans;
54 }
55 long long solve(int x)
56 {
57     if(!x)
58         return 0;
59     dv(x);
60     memset(c,-1,sizeof(c));
61     return dfs(tot,1,k);
62 }
63 void read()
64 {
65     red(l);
66     red(r);
67     red(k);
68     red(b);    
69 }
70 void work()
71 {
72     printf("%lld",solve(r)-solve(l-1));
73 }
74 int main()
75 {
76     input();
77     read();
78     work();
79     return 0;
80 }

View Code

定义c[i][j]表示到第i位时还需要j个数字凑齐