每日一题 day6 打卡
Analysis
题目的意思是找在区间[x,y]之间满足能够由k个b的不同次幂相加得到的数的总数。这题的关键是转换进制，之前几道题我们保存的是数的每位数，其实也就是10进制，这题我们要保存的是b进制，所以在ask函数中要把原来的对10求余和除10都要改成对b进行操作，dp[x][pre]数组表示第x位由pre个b的不同次幂相加得到的数的总数。在判断进入递归的if条件语句中，i的上界要同时满足小于上界且小于等于1，因为根据题意，只有类似3^4次方能够算进去，2*3^4并不能计入，也就是说系数必须小于等于0，且只有等于1时，sta才能增1。还有最后一个要注意的是当x=0递归结束时，只有当pre=k时，才是符合条件的数，ans才能增加。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 #define fa_q 5010 7 using namespace std; 8 typedef long long ll; 9 inline ll read() 10 { 11 ll x=0; 12 bool f=1; 13 char c=getchar(); 14 for(; !isdigit(c); c=getchar()) if(c=='-') f=0; 15 for(; isdigit(c); c=getchar()) x=(x<<3)+(x<<1)+c-'0'; 16 if(f) return x; 17 return 0-x; 18 } 19 inline void write(ll x) 20 { 21 if(x<0){putchar('-');x=-x;} 22 if(x>9)write(x/10); 23 putchar(x%10+'0'); 24 } 25 ll dp[fa_q][fa_q],dim[fa_q]; 26 ll x,y,k,b; 27 ll dfs(int x,int pre,int bj) 28 { 29 if(x==0) return pre==k; 30 if(!bj&&dp[x][pre]!=-1) return dp[x][pre]; 31 int maxn=bj?dim[x]:b-1; 32 ll temp=0; 33 for(int i=0;i<=min(maxn,1);i++) 34 { 35 temp+=dfs(x-1,pre+(i==1),bj&&i==maxn); 36 } 37 if(!bj) dp[x][pre]=temp; 38 return temp; 39 } 40 ll ask(ll x) 41 { 42 dim[0]=0; 43 while(x) 44 { 45 dim[++dim[0]]=x%b; 46 x/=b; 47 } 48 return dfs(dim[0],0,1); 49 } 50 int main() 51 { 52 memset(dp,-1,sizeof(dp)); 53 x=read();y=read();k=read();b=read(); 54 write(ask(y)-ask(x-1)); 55 return 0; 56 }
请各位大佬斧正（反正我不认识斧正是什么意思）