kblack edited 5 年前
This is a past version of blog 《不妙》题解
首先我们将求 $[L, R]$ 的答案转化为求 $[0, R]$ 的答案与 $[0, L-1]$ 的答案之差，只有上界的情况会比较好处理，有上下界也行但是更繁琐没有什么必要。
我们先尝试递归的方法来遍历 $ \leq X $ 的数，方法还是比较显然的，我们将原数按十进制位拆开存入 $num$ 数组中，我们可以通过以下方式遍历：
LL g(int p, bool bound)
{
if (p == 0) return 1;
FOR(i, 0, (bound ? (min(num[p], 9) + 1) : 10))
{
ret += g(p - 1, bound && i == num[p]);
}
return ret;
}
LL ans = g(len, true);
其中 $p$ 表示当前考虑的位数，$bound$ 表示当前考虑的数组是否是顶着上界的（也就是之后需要考虑的数字是否会影响整个数字与上界 $X$ 的大小关系，例如如果上界是 $25$，你现在考虑最高位是 $1$ 那么之后无论怎么选都不用担心超过上界，而如果选择了 $2$ 那么就要担心超过上界），过程就是枚举下一位直到最低为，这样的复杂度显然是 $O(X)$ 的，毕竟每个数字都会且仅会被枚举到一次。
如何改善这个过程？注意到其实有很多部分，我们进行了重复的计算，我们可以考虑对函数的返回值缓存，避免去缓存不能重用的部分。
LL cache[N][M];
LL g(int p, bool bound)
{
if (p == 0) return 1;
if (!bound && cache[p] >= 0) return cache[p];
LL ret = 0;
FOR(i, 0, (bound ? (min(upper[p], 9) + 1) : 10))
{
ret += g(p - 1, bound && i == upper[p]);
}
if (!bound) cache[p] = ret;
return ret;
}
在无限制的情况下，后面的数字都是自由的，显然可以缓存那样的情况，这样一共只会有 $len$ 次函数的调用是无法缓存的，而剩下的 $len$ 种都只会计算一次。
上面算的这个东西很无聊，但是你可以对其方法进行推广。题目中要求不出现 $9$ 且不能被 $9$ 整除，我们只需要在枚举的时候避免枚举到 $9$，计算的过程中记录当前数字数位和模 $9$ 的余数就可以在到底的时候判断是否满足要求。
LL g(int p, int y, bool bound)
{
if (p < 0) return y != 0;
FOR(i, 0, (bound ? (min(upper[p], 8) + 1) : 9))
{
ret += g(p - 1, (y + i) % 9, bound && i == upper[p]);
}
return ret;
}
如何缓存？可以参考上面的方法。