Create a code to determine the amount of integers, lying in the set [ X; Y] and being a sum of exactly K different integer degrees of B. Example. Let X=15, Y=20, K=2, B=2. By this example 3 numbers are the sum of exactly two integer degrees of number 2: 17 = 2 4+2 0, 18 = 2 4+2 1, 20 = 2 4+2 2. Input The first line of input contains integers X and Y, separated with a space (1 ≤ X ≤ Y ≤ 2 31−1). The next two lines contain integers K and B (1 ≤ K ≤ 20; 2 ≤ B ≤ 10). Output Output should contain a single integer — the amount of integers, lying between X and Y, being a sum of exactly K different integer degrees of B. Example input output 15 20 2 2 3
题意：求出X到Y中的，可以由K种B的不同幂次和组成的数的个数
思路：
每次的+Bx看成B进制的X位+1，又幂次不能重复，那就只有01，还是可以看成二进制。枚举每个位0或1即可。套数位dp模板。
AC代码：
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include <queue>
#include<sstream>
#include <stack>
#include <set>
#include <bitset>
#include<vector>
#define FAST ios::sync_with_stdio(false)
#define abs(a) ((a)>=0?(a):-(a))
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define mem(a,b) memset(a,b,sizeof(a))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define rep(i,a,n) for(int i=a;i<=n;++i)
#define per(i,n,a) for(int i=n;i>=a;--i)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std
;
typedef long long ll
;
typedef pair
<ll
,ll
> PII
;
const int maxn
= 1e6+200;
const int inf
=0x3f3f3f3f;
const double eps
= 1e-7;
const double pi
=acos(-1.0);
const int mod
= 1e9+7;
inline int lowbit(int x
){return x
&(-x
);}
ll
gcd(ll a
,ll b
){return b
?gcd(b
,a
%b
):a
;}
void ex_gcd(ll a
,ll b
,ll
&d
,ll
&x
,ll
&y
){if(!b
){d
=a
,x
=1,y
=0;}else{ex_gcd(b
,a
%b
,d
,y
,x
);y
-=x
*(a
/b
);}}
inline ll
qpow(ll a
,ll b
,ll MOD
=mod
){ll res
=1;a
%=MOD
;while(b
>0){if(b
&1)res
=res
*a
%MOD
;a
=a
*a
%MOD
;b
>>=1;}return res
;}
inline ll
inv(ll x
,ll p
){return qpow(x
,p
-2,p
);}
inline ll
Jos(ll n
,ll k
,ll s
=1){ll res
=0;rep(i
,1,n
+1) res
=(res
+k
)%i
;return (res
+s
)%n
;}
inline ll
read(){ ll f
= 1; ll x
= 0;char ch
= getchar();while(ch
>'9'||ch
<'0') {if(ch
=='-') f
=-1; ch
= getchar();}while(ch
>='0'&&ch
<='9') x
= (x
<<3) + (x
<<1) + ch
- '0', ch
= getchar();return x
*f
; }
int dir
[4][2] = { {1,0}, {-1,0},{0,1},{0,-1} };
ll k
, base
;
ll dp
[50][50], a
[50];
ll
dfs(ll pos
, ll k
, bool limit
) {
if (!k
) return 1;
if (pos
< 0) return 0;
if (!limit
&& dp
[pos
][k
] != -1) return dp
[pos
][k
];
ll up
= limit
? a
[pos
] : base
-1;
ll cur
= 0;
for(ll i
=0;i
<=up
&&i
<=1;i
++)
{
cur
+= dfs(pos
-1, k
-i
, limit
&& i
==up
);
}
if (!limit
) dp
[pos
][k
] = cur
;
return cur
;
}
ll
solve(ll x
) {
ll pos
= 0;
while (x
) {
a
[pos
++] = x
% base
;
x
/= base
;
}
return dfs(pos
-1, k
, true);
}
int main() {
mem(dp
,-1LL);
ll L
,R
; L
= read(), R
= read();
k
= read(); base
= read();
cout
<<solve(R
) - solve(L
-1) << '\n';
return 0;
}
