题意:
求给定区间[X,Y]中满足下列条件的整数个数:这个数恰好等于K个互不相等的,B的整数次幂之和。例如,设X=15,Y=20,K=2,B=2,则有且仅有下列三个数满足了要求: 17 = 24+20, 18 = 24+21, 20 = 24+22。(以B为底数,幂次数不允许相同)
参考论文--》》论文中的题。
思路:
论文倒是容易看明白,但是这个转成B进制的思想一直转不过来。其实转成B进制后变成 a1*Bn+a2*Bn-1...an*B0。其中ai是系数。范围是[0,B-1]。但是看了论文知道,里面画的那棵01树(树上的01就是代表系数a),只有从根走到叶子,经过的1的个数为K才是满足要求的。那么如果a大于0怎么办?那么从树上该点开始的整棵子树就可以全部进行考虑了。而如果刚好考虑的位为1的呢?那么取该位为0的那棵子树就行了。
两种实现
//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <map>
#include <algorithm>
#include <vector>
#include <iostream>
#define pii pair<int,int>
#define INF 0x7f3f3f3f
#define LL long long
using namespace std;
const double PI = acos(-1.0);
const int N=; //注意大小 int f[N][N]; void pre_cal() //预处理组合数
{
f[][]=;
for(int i=; i<N; i++) //位数
{
f[i][]=f[i][i]=;
for(int j=; j<i; j++) //多少个1
{
f[i][j]=f[i-][j]+f[i-][j-];
}
}
} int bit[N];
int cal(int n,int k,int b)
{
memset(bit, , sizeof(bit));
int len=, cnt=, ans=;
while(n) //转成b进制
{
bit[++len]=n%b;
n/=b;
}
for(int i=len; i>; i--)
{
if(bit[i]>)
{
ans+=f[i][k-cnt]; //取整棵子树
break;
}
else if( bit[i]== )
{
ans+=f[i-][k-cnt]; //统计左边的
if(++cnt>k) break; //已超
}
}
if(cnt==k) ans++;
return ans;
} int main()
{
//freopen("input.txt","r",stdin);
pre_cal();
int x, y, k, b;
while(~scanf("%d%d%d%d",&x,&y,&k,&b))
printf("%d\n", cal(y,k,b)-cal(x-,k,b));
return ;
}
AC代码
//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <map>
#include <algorithm>
#include <vector>
#include <iostream>
#define pii pair<int,int>
#define INF 0x7f3f3f3f
#define LL long long
using namespace std;
const double PI = acos(-1.0);
const int N=; int f[N][N];
void pre_cal() //预处理组合数
{
f[][]=;
for(int i=; i<N; i++) //位数
{
f[i][]=f[i][i]=;
for(int j=; j<i; j++) //多少个1
{
f[i][j]=f[i-][j]+f[i-][j-];
}
}
}
int bit[N];
int cal(int n,int k,int b)
{
memset(bit, , sizeof(bit));
int len=, cnt=, ans=, flag=;
while(n) //转成b进制
{
bit[++len]=n%b;
n/=b;
if(bit[len]>) flag=;
} if(flag==)
{
//找到第一位大于1的,改为1,然后后面可以全部改成1了
for(int i=len; i>; i--)
if(bit[i]>)
{
for(int j=i; j>; j--) bit[j]=;
break;
}
} for(int i=len; i>; i--)
{
if( bit[i] )
{
ans+=f[i-][k-cnt]; //统计左边的
if(++cnt>k) break; //已超
}
}
if(cnt==k) ans++;
return ans;
} int main()
{
//freopen("input.txt","r",stdin);
pre_cal();
int x, y, k, b;
while(~scanf("%d%d%d%d",&x,&y,&k,&b))
printf("%d\n", cal(y,k,b)-cal(x-,k,b));
return ;
}
AC代码