URAL 1057 Amount of Degrees(数位dp)

题目链接

URAL 1057 Amount of Degrees

题意

求区间$[L,R]$恰好可以用$K$个不相同的$B$的幂次相加得到的数字的个数。
例如：L=15,R=20,K=B=2
$17 = 2^4+2^0$
$18 = 2^4+2^1$,
$20 = 2^4+2^2$
一共有3个。

数据范围：$1\leq L\leq R \leq 2^{31}-1,1\leq K\leq 20,2\leq B\leq 10$

分析

满足区间减法。用$digit[]$数组保存将$x$化为$B$进制数的结果。其实对于最终得到的合法数字，每一位上我们最多只有两种选择：选择0或者选择1。然后我们记录下高位已经选择的结果为$pre$就好了。注意剪枝。

Code

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
using namespace std;
typedef long long ll;int a, b, K, B;
int digit[35], dp[35][35];int dfs(int pos, int pre, int limit)
{if (pre > K || pre + pos + 1 < K) return 0;if (pos == -1) return pre == K;if (!limit && dp[pos][pre] != -1) return dp[pos][pre];int last = limit ? digit[pos] : B - 1, ret = 0;for (int i = 0; i <= min(last, 1); ++i) {  // 有一个限制条件是1ret += dfs(pos - 1, pre + i, limit && (i == last));}if (!limit) dp[pos][pre] = ret;return ret;
}int solve(int x)
{memset(dp, -1, sizeof (dp));memset(digit, 0, sizeof(digit));int len = 0;while (x) {digit[len++] = x % B;x /= B;}return dfs(len - 1, 0, 1);
}int main()
{while (~scanf("%d%d%d%d", &a, &b, &K, &B)) {printf("%d\n", solve(b) - solve(a - 1));}return 0;
}