《不妙》题解 (Past)

kblack edited 4 年,3 月前

This is a past version of blog 《不妙》题解

首先我们将求 $[L, R]$ 的答案转化为求 $[0, R]$ 的答案与 $[0, L-1]$ 的答案之差,只有上界的情况会比较好处理,有上下界也行但是更繁琐没有什么必要。

我们先尝试递归的方法来遍历 $ < 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], 8) + 1) : 9))
    {
        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;
}

如何缓存?可以参考上面的方法。