题意：求出[X, Y]内的可以表示成K个B的不同次幂的和的数的个数。0 <= X <= Y <= 2^31-1，1 <= K <= 20，2 <= B <= 10。
题目链接：http://acm.timus.ru/problem.aspx?space=1&num=1057
——>>做的第一道数位dp题。
思想[X, Y] = [0, Y] - [0, X-1]；
先考虑二进制，求[0, n]：
设f[i][j]表示高度为i的01树中1的个数为j的（根到叶的）路数，递推构造：f[i][j] = f[i-1][j] + f[i-1][j-1]。
模拟n的路，每次右转1时加上左边的符合条件的数的个数。
非二进制的先转化，如n = 34, K = 3, B = 3，34 = 1*3^3 + 2*3^1 + 1*3^0，根据题目可知幂前不能出现系数，所以34不满足条件，那么最接近的满足条件的数，就是第二项改成1*3^1，以及次幂小于1的系数全改成1后的数。
#include <cstdio>using namespace std;int f[40][40];
int to_binary(int n, int B) //B进制转二进制
{int ret = 0, d[40], i, j, m = 0;while(n > 0){d[m++] = n % B;n /= B;}for(i = m-1; i >= 0; i--)if(d[i] > 1){for(j = i; j >= 0; j--)ret |= (1<<j);break;}else{ret |= (d[i]<<i);}return ret;
}
int cal(int n, int K) //不超过n的分成K个幂的数的个数
{int i, cnt = 0, ret = 0;for(i = 31; i > 0; i--){if(n&(1<<i)){cnt++;if(cnt > K) break;n ^= (1<<i);}if(n >= (1<<(i-1))){ret += f[i-1][K-cnt];}}if(cnt+n == K) ret++;return ret;
}
int main()
{int X, Y, K, B, i, j; //f[i][j]表示高度为i的树中有j个1的路f[0][0] = 1, f[0][1] = 0; //初始化for(i = 1; i <= 31; i++){f[i][0] = 1;for(j = 1; j <= i; j++)f[i][j] = f[i-1][j] + f[i-1][j-1];}while(~scanf("%d%d%d%d", &X, &Y, &K, &B)){printf("%d\n", cal(to_binary(Y, B), K)-cal(to_binary(X-1, B), K));}return 0;
}