Ural1057 - Amount of Degrees(数位DP)

时间:2022-03-10 04:26:41

题目大意

求给定区间[X,Y]中满足下列条件的整数个数:这个数恰好等于K个互不相等的B的整
数次幂之和。例如,设X=15,Y=20,K=2,B=2,则有且仅有下列三个数满足题意:

Ural1057 - Amount of Degrees(数位DP)
输入:第一行包含两个整数X和Y。接下来两行包含整数K和B。
输出:只包含一个整数,表示满足条件的数的个数。
数据规模:1 ≤ X ≤ Y ≤ 2^31
−1,1 ≤ K ≤ 20,  2 ≤ B ≤ 10。

题解

《浅谈数位类统计问题》的论问题~~~~~人生第一道数位DP,哈哈~~~O(∩_∩)O~~代码纯属抄袭~~~~

代码:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
using namespace std;
#define MAXN 35
int f[MAXN][MAXN];
void init()
{
f[0][0]=1;
for(int i=1;i<32;i++)
{
f[i][0]=f[i-1][0];
for(int j=1;j<=i;j++)
f[i][j]=f[i-1][j]+f[i-1][j-1];
}
}
int change(int x,int b)
{
int p[MAXN];
int ans=0;
while(x)
{
p[ans++]=x%b;
x/=b;
}
reverse(p,p+ans);
for(int i=0;i<ans;i++)
if(p[i]>1)
{
for(int j=i;j<ans;j++)
p[j]=1;
break;
}
for(int i=0;i<ans;i++)
x=x|(p[ans-i-1]<<i);
return x;
}
int cal(int x,int k)
{
int tot=0,ans=0;
for(int i=31;i>0;i--)
{
if(x&(1<<i))
{
tot++;
if(tot>k) break;
x=x^(1<<i);
}
if((1<<(i-1))<=x)
ans+=f[i-1][k-tot];
}
if(tot+x==k) ans++;
return ans;
}
int main()
{
init();
int x,y,k,b;
while(cin>>x>>y>>k>>b)
{
int X=change(x,b);
int Y=change(y,b);
cout<<cal(Y,k)-cal(X-1,k)<<endl;
}
return 0;
}