URAL 1057 Amount of Degrees
传送门：http://vjudge.net/problem/URAL-1057 题目大意 求一个[x,y]的区间内，有多少个数字满足是K个B的不同次幂相加的和。 题解 按照B进制数位DP即可 代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
#include<cstdio> #include<cstring> #define LL long long using namespace std; int l,r,K,B; int lc[35]; int tot; int num[35]; int F[35][25][2]; int DP(int pos,int pre,int flag){ if (pre>K) return 0; if (pos==0) if (pre==K) return 1; else return 0; if (F[pos][pre][flag]!=0) return F[pos][pre][flag]; int ret=0; int maxNum=flag?num[pos]:B-1; for (int now=0;now<=maxNum&&now<=1;now++) ret+=DP(pos-1,pre+now,flag&&(now==num[pos])); return F[pos][pre][flag]=ret; } inline int calc(int x){ tot=0; while(x){ num[++tot]=x%B; x/=B; } memset(F,0,sizeof(F)); return DP(tot,0,1); } inline void solve(){ printf("%d\n",calc(r)-calc(l-1)); } int main(){ while(scanf("%d%d%d%d",&l,&r,&K,&B)!=EOF) solve(); return 0; } |
