Description
问[L,R]中有多少能表示k个b次幂之和.
Sol
数位DP.
当2进制时.
建出一个二叉树, \(f[i][j]\) 表示长度为 \(i\) 有 \(j\) 个1的个数.
递推式就是左右子树之和 \(f[i][j]=f[i-1][j-1]+f[i-1][j]\)
将b进制变成2进制来做.
因为发现系数只能是1,所以找到一个b进制下极大的2进制就行..我觉得我好像讲不明白..
我计算的是小于 x 满足条件的...我觉得这样比较好写,也不用特判最后的情况..
复杂度 \(O(log^2 n)\)
Code
#include <cstdio>
#include <iostream>
using namespace std; #define debug(a) cout<<#a<<"="<<a<<" "
const int N = 64;
typedef long long LL; LL l,r,k,b;
LL f[N][N]; void init() {
f[0][0]=1;
for(int i=1;i<32;i++) {
f[i][0]=1;
for(int j=1;j<=i;j++) f[i][j]=f[i-1][j]+f[i-1][j-1];
}
// for(int i=0;i<6;i++) {
// for(int j=0;j<=i;j++) cout<<f[i][j]<<" ";cout<<endl;
// }
}
LL calc(LL x) {
LL t=1,r=0,c=0;
for(;t<x;t*=b,c++);
for(;x;t/=b,c--) if(x>=t) {
if(x>=2*t) {
return r+(1<<(c+1))-1;
}else {
x%=t,r+=1<<c;
}
}
return r;
}
int DP(LL x) {
int r=0,c=k;
for(int i=31;~i;i--) {
if(x & (1LL<<i)) {
if(c>=0) r+=f[i][c];
c--;
// debug(i),debug(f[i][c])<<endl;
}
}return r;
}
int main() {
// freopen("in.in","r",stdin);
init(); cin>>l>>r>>k>>b; // debug(calc(r)),debug(calc(l-1))<<endl;
// debug(DP(calc(r))),debug(DP(calc(l-1)))<<endl; cout<<DP(calc(r+1))-DP(calc(l))<<endl;
return 0;
}