K个互不相同的B的整数次幂，等价于求数字num在B进制表示下是否是由K个1且其他位全是0组成，可用数位Dp来做。
我们把数字 n 对于B进制来进行分解 ，将每一位上的数字存入一个数组中，然后从高位往低位去讨论，
首先 对于第 i 位数字 x 有三种情况
时刻要记住，我们的任务是要选k个1，枚举的那一位有两种情况，是1和不是1，不是1的话有=0和>1两种情况，是1的话情况要更细讨论。
1. x = 0 ：则 i 位上只能取 0 ，所以直接讨论 i-1 位就可以了
2. x = 1 ：则 i 位上取 0 的时候，后面i-1位都可以随意取值，取1的时候，后面i-1位要再小于题目的数的前提下取值，并且能取 k-last-1 个 1 。填1的话，就说明an-1这一位已经没有前途了，last++之后继续向下位枚举
3. x > 1 ：则 i 位上 可以取 1，0，并且后面i-1位可以随便取。就是说，如果枚举到一位是大于1的，就美滋滋，方案数一下就算出来了（且这些方案中的数，一定比n小）
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
const int N=35;
int f[N][N];
int k,b,l,r;
int dp(int n)
{
if(n==0) return 0;
vector<int> nums;
while(n)
{
//转换为b进制
nums.push_back(n%b);
n=n/b;
}
int res=0;
//记录已经用了多少1
int last=0;
//一般从最高位开始枚举
for(int i=nums.size()-1;i>=0;i--)
{
int x=nums[i];
//如果x不等于0，求左边分支的数的个数
//左边分支有两种情况
//1.x = 1 ：则 i 位上取 0 的时候，后面i-1
//位都可以随意取值 ；取 1 的时候，后面i- 1位要再小于题目的数的前提下取值，并且能取 k-last-1 个 1
// 这个else 是x==1，
//对应于：右分支为1的情况，即限定值为1的情况，也就是左分支只能取0
////此时的处理是，直接放到下一位来处理。只不过下一位可使用的1的个数会少1，体现在代码上是last+1
if(x)
{
res+=f[i][k-last];
if(x>1)
{
if(k-last-1>=0)
{
res+=f[i][k-last-1];
}
break;
}
else
{
last++;
if(last>k) break;
}
}
//枚举到最后，如果成功了，算一种
//如1001，最后一个1再最后，而其他位置上都是0，必须要等到最后一个1出来才能算一种
if(i==0 && last ==k) res++;
}
return res;
}
int main()
{
for(int i=0;i<=N;i++)
{
for(int j=0;j<=i;j++)
{
if(j==0) f[i][j]=1;
else
f[i][j]=f[i-1][j]+f[i-1][j-1];
}
}
cin>>l>>r>>k>>b;
cout<<dp(r)-dp(l-1);
return 0;
}
数位dp的核心思想：
- 利用前缀和，比如求区间[x,y]中的个数，转化成求[0,y]的个数 -[0,x-1]的个数。
- 利用树的结构来考虑（按位分类讨论,左边为0~an-1，右边为an，其中an为当前位的数）
对于B进制数N（共n位），从最高位（第n位）开始遍历每1位，对于第 i 位，last表示第i位之前的所有位取过的1的个数。第i位上的数字x有三种情况：
1. 限定值x=0：此时第i位只能取0，不影响1的个数，后面所有位可以取k-last个1。
2. 限定值x=1：此时可以取0或1.当此位取0时，后面的所有位可以取k -last个1；当此位取1时，后面所有位只能取k -last -1个1.
3. 限定值x>1： 当前位取0或1时，处理同2；其他值直接不能取，在本题中没意义。
另外注意，此题按位遍历时，if中的执行为break，意思为直接算完了，可以不用继续遍历了。
只有在x=1(第i位本身就为1的情况)，才会继续遍历
有个超级大坑！！
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
const int N=35;
int f[N][N];
int k,b;
int L,R;
int dp(int n)
{
vector<int> num;
while(n)
{
num.push_back(n%b);
n=n/b;
}
int res=0;
int last=0;
for(int i=num.size()-1;i>=0;i--)
{
int x=num[i];
if(x>0)
{
//先枚举让第i位=0的情况
res+=f[i][k-last];
if(x>1)
{
// 第i为大于1，就让第i位取1，直接算完了，算完break
if(k-last-1>=0) res+=f[i][k-last-1];
break;
}
else
{
//第i为=1的情况
last++;
if(last>k) break;
}
}
if(i==0 && last == k) res++;
}
return res;
}
int main()
{
cin>>L>>R>>k>>b;
// 此处一定要是N-1!!!!!，如果是N的话，由于数组会越界，且k,b,l,r定义在数组之后，那么这块的地址就会修改k,b,l,r的值
for(int i=0;i<=N-1;i++)
{
for(int j=0;j<=i;j++)
{
if(j==0) f[i][j]=1;
else
f[i][j]=f[i-1][j]+f[i-1][j-1];
}
}
cout<<dp(R)-dp(L-1);
return 0;
}
三刷，之前又忘了，又复习一遍
分三种情况，x>1,x=1,x=0来考虑
数位dp按位讨论，从高位往低位
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
const int N=35;
int f[N][N];
int k,b;
int L,R;
int dp(int n)
{
vector<int> num;
int res=0;
while(n)
{
num.push_back(n%b);
n=n/b;
}
int last=0;
for(int i=num.size()-1;i>=0;i--)
{
int x=num[i];
if(x>0)
{
//先枚举x=0的情况，即最高位为0，剩下的1在后面的位数取，这个情况可以直接算出来
//因为我的最高位是>0的，我现在让最高位=0，所枚举的数一定是合法的，直接在剩下的位数中选k-last个位置放1即可
res+=f[i][k-last];
if(x>1)
{
//如果这一位是大于1的，那嗷嗷叫直接结束，让这一位等于1(用掉一个1)再把k-last-1个数分给剩下的位，直接结束
if(k-last>=1)
res+=f[i][k-last-1];
break;
}
else
{
last++;
if(last>k) break;
}
}
if(i==0&& last==k ) res++;
}
return res;
}
int main()
{
cin>>L>>R>>k>>b;
for(int i=0;i<=N-1;i++)
{
for(int j=0;j<=i;j++)
{
if(j==0) f[i][j]=1;
else
f[i][j]=f[i-1][j]+f[i-1][j-1];
}
}
cout<<dp(R)-dp(L-1);
return 0;
}
