[UOJ #140]【UER #4】被粉碎的数字

题目大意：定义$f(x)$为数字$x$每一位数字的和，求$\sum\limits_{i=1}^R[f(x)=f(kx)]$。$R\leqslant10^{18},k\leqslant10^3$

题解：数位$DP$，从低位到高位$DP$，定义$f[i][j][x][y]$为从低到高第$i$位，$j=f(a\bmod{10^i})-f(ka\bmod{10^i})$，$ka\equiv x\pmod{10^i}$，$y=[a>(R\bmod{10^i})]$，转移显然。注意到$ka$位数大于$a$导致$DP$不全，可以添加$R$的位数（因为$k\leqslant10^3$，就添加$3$位）

卡点：无

 

C++ Code：

#include <cstdio>
#include <iostream>
#include <algorithm>

int k, num[30], tot;
long long f[30][500][1000][2], x;
int main() {
	std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);
	std::cin >> x >> k;
	while (x) num[++tot] = x % 10, x /= 10;
	tot += 3;
	f[0][250][0][0] = 1;
	for (int i = 0; i < tot; ++i)
		for (int j = -200; j <= 200; ++j)
			for (int x = 0; x < 1000; ++x)
				for (int y = 0; y < 2; ++y) if (f[i][j + 250][x][y]) {
					for (int z = 0; z < 10; ++z)
						f[i + 1][j + z - (k * z + x) % 10 + 250][(k * z + x) / 10][z == num[i + 1] ? y : z > num[i + 1]] += f[i][j + 250][x][y];
				}
	std::cout << f[tot][250][0][0] - 1 << '\n';
	return 0;
}