5.2 KiB
1799. [Ahoi2009] self 同类分布
一、题目描述
给出 a,b，求出[a,b]中各位数字之和能整除原数的数的数字个数。
其中1≤a≤b≤10^{18}
二、解题思路
我们来思考此题目的状态表示应该和哪些因素有关：
-
数位
pos这个是最无脑的，数位dp都得有这个。 -
数字前序
pre(十进制表示) -
数位和
sum枚举数位和 因为总共就18*9=162,然后问题就变成了一个数\%mod=0，mod是枚举的。想到这两个也不是什么难事，最终需要我们计算原数是否能整除掉数位和，不记录数位和记录啥？
想想状态：
dp[pos][sum][pre]，当前pos位上数位和是sum,pre就是在算这个数\%mod,(从高位算*10+i)，因为我们枚举的数要保证数位和等于mod，还要保证这个数是mod的倍数，很自然就能找到这些状态。
此题的难点
pre是必须要携带的信息，否则最后无法计算是不是能整除掉sum,但是，由于pre最终就是原来的数字，范围是<=1e18,很显然不能做为状态，而且，如果做了状态，也就起不到按集合聚合结果的作用，就真的成了无法记忆化了。
所以，我们需要想办法把pre化成集合的形式！
套路
一般的，如果题目中有取模这样的含义，通常是按模分组，也就是按模进行划分集合。叫套路有些技术含量太low,那就叫做经验吧~
如此，我们在每一步计算出pre时，就不断的在运算过程中取模再保存状态，成功的将单个数字化为集合形式~
背后的原因：最后的目标并不是真的需要pre，而是需要问 sum \mid pre 还是 sum \nmid pre!我们可以理解为不用真的传递原始类前缀和(就让我先这样叫它吧，含义你懂的),而是传递了类前缀和\% ~ mod的值，这样，如果pre中有整数个mod,就会被拿下，只保留余数，但并不影响最终判断是不是能整除mod,好处就是每次传递的数字一下就下降到mod-1及以下，没有溢出等烦恼。体现在本题中，如果我们傻傻的强行设计状态\large f[20][N][1e18]
不就MLE炸掉了吗？当然，这样也没法按集合思路进行记忆，肯定是不中的，需要对pre \% mod进行分组~！
其它思路
显然对于每一个mod，pre不能保证状态唯一，这是你要是想加一维dp[pos][sum][val][mod],记录每一个mod的状态(这里sum可以用减法，然而val不行，就只能加一维)，那你就想太多了，这样是会超时的(因为状态太多，记忆化效果不好)。这里直接对每一个mod，memset一次就能ac。
三、实现代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
using namespace std;
typedef long long ll;
const int N = 170;
int a[20], mod;
/*
f[pos][sum][pre]
第一维：数字的每一位，从18~1有效
第二维：已经走完的路径，每位的数位和
第三维：已经走完的路径，每位的拼接值(十进制)
前提：已经走到pos这个位置，前面积累下来的数位和是sum,前面的数字拼接pre(10进制), (是不是贴上界)
返回：在满足前提条件下，后续符合题意的数字有多少个？
*/
ll f[20][N][N];
//此处注意一下：pre如果是类型ll,则会第9个点TLE，是类型int,则可以AC!
ll dfs(int pos, int sum, int pre, bool limit) {
// 如果走完了全程，pre=原数%mod,如果最后pre还能整除mod,并且，sum等于mod,则贡献数字1个
if (pos == 0) return pre == 0 && sum == mod;
if (!limit && ~f[pos][sum][pre]) return f[pos][sum][pre];
ll ans = 0;
int up = limit ? a[pos] : 9;
for (int i = 0; i <= up; i++) {
// sum+i:数位和+i
// (pre * 10 + i) % mod : 不断的拼接前缀数字(十进制)，但不能盲目记录原始数字，需要分组，按什么分组呢？当然是按枚举的当前mod分组
// 上面这句是本题的精华！
ans += dfs(pos - 1, sum + i, (pre * 10 + i) % mod, limit && i == a[pos]);
}
//记忆化结果
if (!limit) f[pos][sum][pre] = ans;
return ans;
}
ll calc(ll x) {
if (x == -1) return 0; //处理一下边界情况
int al = 0;
while (x) a[++al] = x % 10, x /= 10;
ll res = 0;
for (mod = 1; mod <= 9 * al; mod++) { // max(mod)=9*18=162,数量并不大，可以枚举
memset(f, -1, sizeof f); //每次取的模都会变化，这样状态数组就不再可以重用，需要每次清空
res += dfs(al, 0, 0, true); //其实本题的本质是按分组讨论的方式完成的数量的统计，然后再汇总总数量
}
return res; //返回结果
}
int main() {
ll l, r;
scanf("%lld%lld", &l, &r);
printf("%lld\n", calc(r) - calc(l - 1));
return 0;
}