【题解】CF1985G D-Function

Before

由于数的位数很大，我们用 ${\textstyle \sum_{i = 0}^{n} a_i \times 10^i}$ 来表示一个 $n + 1$ 位的数，那么 $D(num) = {\textstyle \sum_{i = 0}^{n} a_i}$​ 就是这个数的数位之和。

Solution

敲份暴力代码不难发现以下结论：

对于任意的 $num \in \left [ 10^l, 10^r \right )$，当且仅当 $num \times k$ 的任意一位上没有发生进位，满足 $D(k \times num) = k \times D(num)$。

证明：因为 $D(num) = {\textstyle \sum_{i = 0}^{n} a_i}$，$k \times D(num) = {\textstyle \sum_{i = 0}^{n} a_i \times k}$。只要 $num$ 上的第 $i$ 位发生了一次进位，说明第 $i - 1$ 位上的数位减少了 $10$，而第 $i$ 位上的数位增加了 $1$，这在数值上的贡献显然为 $0$，但是对于数的位数贡献为 $-9$，由上式可知 $num \times k$ 上的任意一位要严格为 $num$ 相应位上的 $k$ 倍，因此不允许发生任何进位。

接下来考虑的事情就十分简单，每一位上满足不进位的数是固定的：$t = \left \lceil \frac{10}{k} \right \rceil$（例如 $k = 3$ 时可以填入 $0,1, 2, 3$），而对于 $num \in \left [ 0 , 10^n \right )$，满足条件的 $num$ 的个数即为 $t^n$，快速幂计算即可。

又由于 $num$ 的范围有着左闭右开的特点，我们不难想到用类似前缀和的思路分别计算从 $0$ 到 $l$ 和 $r$ 的个数，相减即可，即：

$$ans \left [ l, r \right ) = ans \left [ 0, r \right ) - ans \left [0, l \right )$$

单次时间复杂度：$\mathcal{O} (r \log r)$。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

int ksm(int a, int b)
{
    int res = 1;
    while (b)
    {
        if (b & 1) res = a * res % mod;
        a = a * a % mod, b >>= 1;
    }
    return res % mod;
}

inline int calc(int x) { return ksm(times, x); }

void solve()
{
    cin >> l >> r >> k;
    times = (10 + k - 1) / k;	// 向上取整
    
    cout << (calc(r) - calc(l) + mod) % mod << '\n';	// 涉及减法的取模务必加模再取以防止出现负数
}