数位DP

1. 什么是数位DP

数位DP：对数字在位的层次上用动态规划的方法进行优化

2. 理解方式

现在有一个需求：
  求给定区间 [X,Y] 中满足下列条件的整数个数：这个数恰好等于 K 个互不相等的 B 的整数次幂之和。例如，设 X=15,Y=20,K=2,B=2，则有且仅有下列三个数满足题意：求[0, v]中的数满足：这个数恰好等于 K 个互不相等的 B 的整数次幂之和 的个数

本题的本质还是:枚举
具体来说，就是一位一位地从0到Max进行枚举，根据每一位地值，在满足要求地基础上(不超过Max)按情况枚举、讨论

例如：

17 = 2 ^ 4 + 2 ^ 0
18 = 2 ^ 4 + 2 ^ 1
20 = 2 ^ 4 + 2 ^ 2

3. 题目分析

(1) 首先，观察得到，样例中的每一位权积前面的系数都是 1 且位权都是2的几次方,所以可以想到，只要枚举[0, v]中满足该条件的就可。
(2) 其次,K相当于限制了1的被枚举的数中1的个数; B则代表进制
(3) 定义 f[i][j] = f[i - 1][j - 1] + f[i - 1][j] 为从i 个位置选择j个位置插入1
(4)分析：
从高位开始枚举，设第i位为x
(1)当x等于0时，跳过，枚举下一位，因为当前枚举出来的数不能超过Max(即给定的值也是dp()函数中的参数)
(2)当x等于1时

• 如果当前位置放0,那么满足要求：不超过Max那么res += f[i - 1][K - t] K是题目给定的，t代表在该位前面i - 1位中，含1的数量
• 如果当前位置放1,后面的无法按照组合数公式表示，所以该位置为1，且t ++

(3)当x大于1时

• 如果当前位置放0,那么满足要求：不超过Max那么res += f[i - 1][K - t]
• 如果当前位置放1,后面的值res += f[i - 1][K - t - 1]
• 如果当前位置放大于1的值，不满足要求，因为题目中的意思要求位权积前面的系数都为1

代码实现

#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long int llint;
typedef pair<int, int>PII;

int x, y, m, n, k, b;
const int N = 33;
int a[N];
int f[N][N];//f[i][j]代表从i个位置中，选择j个置为1
/*
组合数公式: f[i][j] = f[i - 1][j] + f[i - 1][j - 1];
*/
void init()
{
	for (int i = 0; i < N; i ++ ) f[i][0] = 1;
	for (int i = 1; i < N; i ++ )
	{
		for (int j = 1; j <= i; j ++) f[i][j] = f[i - 1][j - 1] + f[i - 1][j];
	}
}
int dp(int v)
/*
dp[v]含义:[0, v]中的数满足：这个数恰好等于 K 个互不相等的 B 的整数次幂之和 的个数
*/
{
	if (!v) return 0;
	int cnt = 0, res = 0, t = 0;
	while (v) a[ ++ cnt] = v % b, v /= b ;
	for (int i = cnt; i >= 1; i -- )
	{
		int value = a[i];

	 	if(value)
		{
			res += f[i - 1][k - t];//因为都要有这一步，所以直接拿出来先加上 
			if (value == 1)
			{
				t ++;
				if (t > k) break;
			}
			if (value > 1) 
			{
				if (k - 1 >= t) res += f[i - 1][k - 1 - t];
				break;
			}
		}
		if ( i == 1 && t == k) res ++;
	}
	return res;
}
int main()
{
	ios::sync_with_stdio(false);
	init();
	cin >> x >> y;
	cin >> k >> b;
	cout << dp(y) - dp(x - 1) << endl;
	return 0;
}