我觉得这位大佬说的已经很好了,可以直接看她的思路了;
大佬思路
但是她的代码没有考虑到1 1 1 1的情况,
代码思路
这个是可以的很长且没有注释;
#include<bits/stdc++.h>
using namespace std;
long long d[40][40];
long long c[40][40];
long long a[40];
long long x,y;
int k,b;
long long makedp(int i,int j,long long sub){
//该函数表示从i个位置当中选j个位置赋值为1且小于等于sub;
if(i==0){
if(j==0&&sub==0){
return 1;
}
else return 0;
}
if(i<j){//不够要求
return 0;
}
if(sub==0){
if(j==0){
return 1;//找0位
}
else{
return 0;
}
}
else if(sub>=d[i][j]){
//这里很好的避免了重复;
return c[i][j];//最大,就找小于他的最多
}
long long sum=0;
sum+=makedp(i-1,j,sub);//取消最高位太大减小
sum+=makedp(i-1,j-1,sub-a[i]);//在保证最高位在的情况
return sum;
}
void init(){
memset(a,0,sizeof(a));
memset(d,0,sizeof(d));
long long t=1;
a[1]=t;
for(int i=2;i<=32;i++){
t=t*b;
if(t>y){
break;
}
a[i]=t;//a数组表示的是b^(i-1);
}
d[1][1]=1;
for(int i=2;i<=32;i++){
if(a[i]==0){
break;
}
for(int j=1;j<=i;j++){
//d=b^(i-1)+b^(i-2)+..有j个元素
d[i][j]=d[i][j-1]+a[i-j+1];
}
}
}
int main(){
for(int i=0;i<=32;i++){
c[i][0]=1;
}
//这里表示的是组合数,
//从i位数中取出j个来。
for(int i=1;i<=32;i++){
for(int j=1;j<=i;j++){
c[i][j]=c[i-1][j]+c[i-1][j-1];
}
}
while(~scanf("%lld%lld%d%d",&x,&y,&k,&b)){
init();
int u;
for(int i=1;i<=32;++i){
//找到不超过y的b^(i-1)
if(a[i]>y){
u=i-1;//所以减一
break;
}
else if(a[i]==0){
u=i-1;
break;
}
}
long long t1=makedp(u,k,y);
for(int i=1;i<=32;++i){
if(a[i]>x-1){
u=i-1;
break;
}
else if(a[i]==0){
u=i-1;//超出2
break;
}
}
long long t2=makedp(u,k,x-1);
//适用减法行为
cout<<t1-t2<<endl;
}
return 0;
}
标签:sub,int,40,ZCMU,break,long,1033,makedp
From: https://www.cnblogs.com/hai-zei/p/18114964