2018-01-12

数位DP

使用范围

对于区间 $[ l, r ]$ 中，求满足 $f(i)$的数的个数

通常 $f(i)$ 与数的大小没有关系，与数位上的数字有关

写法

有记忆化搜索和传统dp两种写法，不过一般好像都是写的前者，比较容易编写且没有太多的细节。

一般形态

$dfs(int pos, int tot, int ok, bool lim )$

表示处理到第 $pos$ 位且前面的贡献是 $tot$, 和目标的表较量 $ok$, 以及最后的关于数的限制 $lim$。

一道题目

给出a,b，求出[a,b]中各位数字之和能整除原数的数的个数。

这是一道裸题，直接套函数即可。
说一下 $lim$ 的用法，这里的限制是当前枚举的数字不能超过 $num$,那么如果枚举到了 $num$的有效位，如果枚举的数字 $c$ 小于 $num[pos]$ ,直接退出，如果等于则在下一层中仍有可能越界，否则不越界。

代码：

#include <cstdio>
#include <cstring>
#include <iostream>
typedef long long LL;
LL pow[20], f[20][165][165][2];
bool vis[20][165][165][2];
//pos -> 枚举数位  tot -> 数位之和  rem -> 答案  lim -> 限制 
inline LL dfs(int pos, int tot, int rem, bool lim, int sum ,LL num){
	if (vis[pos][tot][rem][lim])
		return f[pos][tot][rem][lim];
	vis[pos][tot][rem][lim] = true;
	f[pos][tot][rem][lim] = 0;
	if(pos == 0) return f[pos][tot][rem][lim] = ((rem == 0) && (tot == sum));
	for (int i = 0; i < 10; i++){
		int c = num / pow[pos - 1] % 10;
		if (i + tot > sum || lim && c < i) break;
		LL tmp = dfs(pos - 1, tot + i, (rem * 10 + i) % sum, lim && c == i, sum ,num);
		f[pos][tot][rem][lim] += tmp;
	}
	return f[pos][tot][rem][lim];
}
inline LL calc(LL x) {
	LL rtn = 0;
	for (int i = 1; i <= 162; i++) {
		memset(vis, false, sizeof(vis));
		rtn += dfs(19, 0, 0, true, i, x);
	}
	return rtn;
}
int main(){
#ifdef YSW 
	freopen("data.in", "r", stdin);
#endif
	pow[0] = 1;
	for(int i = 1; i <= 19; i++) pow[i] = pow[i-1] * 10;
	LL l, r; scanf("%lld%lld", &l, &r);
	printf("%lld", calc(r) - calc(l - 1));
	return 0;
}