形式化题目

给定正整数 $l, r, k$（$1 \leqslant l \leqslant r$），统计 $k$ 进制下位数在 $[l,r]$ 之间、且数位和能被 4 或 5 或 6 整除的整数个数，答案模 $10^9+7$。题面里的"幸运数字 546 的倍数"只是背景故事，与所求无关。

第一步是把"位数"翻译成"数值区间"：$k$ 进制下 $n$ 位数的取值范围是 $[k^{n-1}, k^n)$（$n \geqslant 1$，0 不算 1 位数），于是位数在 $[l,r]$ 的数就是数值落在 $[k^{l-1}, k^r)$ 中的数。再注意到高位补零不改变数位和：把每个数补零到固定长度后，"数值在 $[0,k^n)$ 内"与"长度恰为 $n$ 的数字串（允许前导零）"一一对应。记

所求就是 $G(r) - G(l-1)$：大区间 $[0,k^r)$ 减去前缀 $[0,k^{l-1})$。

样例解释：

• 样例 #1（1 5 2）：区间 $[1,32)$。二进制数位和为 4 的有 15、23、27、29、30，为 5 的有 31，共 6 个。用 $G$ 算：$G(5) = 7$（多出的 1 个是 0），$G(0) = 1$（空串对应数值 0），$7 - 1 = 6$。
• 样例 #2（8 8 2）：区间 $[128,256)$，最高位必为 1，剩余 7 位中放 $m$ 个 1，数位和 $1+m \in \{4,5,6,8\}$，即 $m \in \{3,4,5,7\}$，共 $\binom{7}{3}+\binom{7}{4}+\binom{7}{5}+\binom{7}{7} = 35+35+21+1 = 92$；等价地 $G(8)-G(7) = 156-64 = 92$。

正解

思路

朴素做法与瓶颈。 直接枚举 $[k^{l-1}, k^r)$ 里的每个数求各位和：区间里有 $k^r - k^{l-1}$ 个数，$k$、$r$ 都到 $10^{18}$，完全不可行。退一步改成逐位 DP：记 $f[n][s] =$ 前 $n$ 位、数位和恰为 $s$ 的方案数，转移要枚举下一位的每个数字 $d \in [0,k)$，即 $f[n+1][s+d] \mathrel{+}= f[n][s]$。三个维度同时爆炸：层数 $n$ 到 $10^{18}$，单层转移要枚举 $k$ 到 $10^{18}$ 个数字，$s$ 的上界 $n(k-1)$ 更是天文数字。下面依次砍掉这三个维度。

观察一：判定只需要数位和模 60。 因为 $4,5,6$ 都整除 $60 = \mathrm{lcm}(4,5,6)$，所以"被 4/5/6 之一整除"完全由 $s \bmod 60$ 决定。合法余数集合 $S = \{i : i\%4=0 \lor i\%5=0 \lor i\%6=0\}$，用容斥算出 $15+12+10-3-5-2+1 = 28$ 个。于是把状态从"精确数位和"压成"数位和模 60"，只剩 60 个状态：记 $\mathrm{dist}_n[i] =$ 长度 $n$、数位和 $\equiv i \pmod{60}$ 的串数，初值 $\mathrm{dist}_0 = [1,0,\dots,0]$（空串）。

观察二：转移不枚举数字，只用 60 个计数。 加一位数字 $d$ 后状态从 $i$ 走到 $(i+d) \bmod 60$，作用只取决于 $d \bmod 60$，所以按余数分类计数：

（$[\cdot]$ 是 Iverson 括号：条件成立取 1，否则取 0。）

以真实数据里的 $k = 906$（$906 = 60 \times 15 + 6$）为例，看这 60 个计数从哪来：

每个余数先摊 $\lfloor k/60 \rfloor$ 轮完整周期（每轮 60 个数各贡献一次），前 $k \% 60$ 个余数再多一个。转移于是变成只含这 60 个系数的式子：

即 $\mathrm{dist}_{n+1} = \mathrm{dist}_n \circledast c$，是模 60 的循环卷积：单层只要 $O(60^2)$ 次乘加，且与 $k$ 的大小无关——观察二同时消掉了"枚举 $k$ 个数字"这个维度。

观察三：每层转移相同且线性，用快速幂跨过 $10^{18}$ 层。 连续加 $n$ 位等价于 $\mathrm{dist}_n = c^{\circledast n}$（$c$ 自己卷 $n$ 次）。卷积满足结合律、单位元是 $\delta_0$，所以用倍增求：层数不断平方、按 $n$ 的二进制位把层乘进结果，只需 $O(\log n)$ 层——"层数到 $10^{18}$"这个维度被对数消掉。

观察四：循环矩阵结构，不必写 $60\times60$ 矩阵乘法。 上述递推等价于矩阵 $A[i'][i] = c_{(i'-i) \bmod 60}$ 的 $n$ 次幂作用在 $\mathrm{dist}_0$ 上。$A$ 的元素只依赖下标之差，是循环矩阵，而 $A^n$ 的第 0 列恰好等于 $c^{\circledast n}$。所以标准的 $60\times60$ 矩阵快速幂（每层 $O(60^3)$）可以直接换成 60 维向量的循环卷积快速幂（每层 $O(60^2)$）——这就是代码里的 conv + pow_dist。

小规模演进（$k=2$，样例 #1）。 此时 $c = [1,1,0,\dots,0]$，且数位和最大为 $5 < 60$，取模不改变数值，分布恰好是二项式系数：

每行是上一行与 $c$ 做循环卷积的结果（这里 $c$ 只有 $t=0,1$ 两项为 1，即每个数往自己和"自己加 1"两个方向各转移一次）。合法列只统计命中 $S$ 的余数 $0,4,5$（$1,2,3 \notin S$）。最后一行 $G(5) = 1+5+1 = 7$，答案 $G(5)-G(0) = 7-1 = 6$，与样例 #1 一致。

收尾与边界。 求 $G(r)$、$G(l-1)$ 各做一次卷积快速幂，输出 $(G(r) - G(l-1)) \bmod 10^9+7$。$l = 1$ 时 $G(0) = 1$ 正好把数值 0 排除（0 不是 1 位数，样例 #1 已验证题面口径）；$k < 60$ 时 $\lfloor k/60 \rfloor = 0$、$c_t = [t<k]$；$k$ 是 60 的倍数时 $k\%60=0$、没有 $+1$ 分支——公式在这些边界都自然成立。

代码

Python 版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 19:05
# update_at: 2026-10-02 19:05

import sys

MOD = 10**9 + 7
M = 60  # lcm(4,5,6)：数位和只要模 60，就能判断是否被 4/5/6 中某个数整除


def conv(a: list[int], b: list[int]) -> list[int]:
    """两个「数位和模 60 分布」的循环卷积：先累加、最后一次取模。"""
    acc = [0] * M
    for i, x in enumerate(a):
        if not x:
            continue  # 空档跳过，省掉一半内层循环
        for j, y in enumerate(b):
            if y:
                acc[(i + j) % M] += x * y
    return [v % MOD for v in acc]


def pow_dist(base: list[int], n: int) -> list[int]:
    """初始分布 base 做 n 次循环卷积（快速幂）：恰好 n 位的数位和模 60 分布。"""
    res = [1] + [0] * (M - 1)  # 单位元：0 位、数位和为 0
    while n:
        if n & 1:
            res = conv(res, base)
        base = conv(base, base)
        n >>= 1
    return res


def count_good(step: list[int], n: int) -> int:
    """恰好 n 位（允许前导零）的 k 进制数里，数位和被 4/5/6 整除的个数。"""
    dist = pow_dist(step, n)
    return sum(v for i, v in enumerate(dist) if i % 4 == 0 or i % 5 == 0 or i % 6 == 0) % MOD


def solve() -> None:
    l, r, k = map(int, sys.stdin.buffer.read().split())

    # 一位数字 d（0 <= d < k）贡献的数位和增量 d mod 60：每个余数先摊 k//60 个，
    # 余下 k%60 个（即 0..k%60-1 这些余数）各再多一个。
    quota, extra = divmod(k, M)
    step = [quota + (1 if i < extra else 0) for i in range(M)]  # 60 项

    # l 位数到 r 位数 = 数值落在 [k^(l-1), k^r) 的数；高位补零到 r 位后数位和不变，
    # 于是答案 = 恰好 r 位的合法个数 - 恰好 l-1 位的合法个数（被减掉的是更短前缀）。
    print((count_good(step, r) - count_good(step, l - 1)) % MOD)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-04 23:13
 * update_at: 2026-10-04 23:13
 */
// main.cpp：k 进制 l~r 位数中数位和被 4/5/6 整除的数的个数（模 1e9+7）。
// 思路：答案 = G(r) - G(l-1)，G(n) 为 [0,k^n) 中合法数的个数；
// 判定只看数位和模 lcm(4,5,6)=60，一步转移是模 60 的循环卷积，
// 层数到 1e18，用卷积快速幂（循环矩阵性质，每层 O(60^2)）跨过去。

#include <cstdio>

typedef long long ll;

const ll MOD = 1000000007LL;
const int M = 60; // lcm(4,5,6)，数位和模 60 即可判定合法性

// 计数器按数位和模 60 的余数保存分布，固定 60 项，全局数组
ll dist[M];       // 当前分布：dist[i] = 数位和 ≡ i (mod 60) 的串数
ll base_dist[M];  // 快速幂中不断平方的底向量
ll result_dist[M]; // 快速幂累乘的结果向量
ll tmp_dist[M];   // 卷积结果的临时数组

ll l, r, k; // 输入：位数区间 [l,r]，进制 k（都可能到 1e18）

// 两个「数位和模 60 分布」做循环卷积，结果存到 out
void conv(ll a[], ll b[], ll out[]) {
    for (int i = 0; i < M; ++i) out[i] = 0;
    for (int i = 0; i < M; ++i) {
        if (a[i] == 0) continue; // 空档跳过，省内层循环
        for (int j = 0; j < M; ++j) {
            if (b[j] == 0) continue;
            int pos = i + j;
            if (pos >= M) pos -= M; // 模 60，用减法代替取模更快
            out[pos] = (out[pos] + a[i] * b[j]) % MOD;
        }
    }
}

// 初始分布 src 自卷 n 次（快速幂），结果存回 src
void pow_dist(ll src[], ll n) {
    // 结果向量置为单位元：0 位、数位和为 0
    for (int i = 0; i < M; ++i) result_dist[i] = 0;
    result_dist[0] = 1;
    for (int i = 0; i < M; ++i) base_dist[i] = src[i];
    while (n > 0) {
        if (n & 1) {
            conv(result_dist, base_dist, tmp_dist);
            for (int i = 0; i < M; ++i) result_dist[i] = tmp_dist[i];
        }
        conv(base_dist, base_dist, tmp_dist);
        for (int i = 0; i < M; ++i) base_dist[i] = tmp_dist[i];
        n >>= 1;
    }
    for (int i = 0; i < M; ++i) src[i] = result_dist[i];
}

// 恰好 n 位（允许前导零）的 k 进制数里，数位和被 4/5/6 整除的个数
ll count_good(ll n) {
    // 生成一位数字的余数分布 step：每个数字 d (0<=d<k) 贡献 d mod 60，
    // 每个余数先摊 k/60 个，余下前 k%60 个余数各再多一个
    ll step[M];
    ll quota = k / M, extra = k % M;
    for (int i = 0; i < M; ++i) step[i] = quota + (i < extra ? 1 : 0);
    pow_dist(step, n);
    // 合法余数集合：被 4 或 5 或 6 整除的 i (0<=i<60)，共 28 个
    ll sum = 0;
    for (int i = 0; i < M; ++i)
        if (i % 4 == 0 || i % 5 == 0 || i % 6 == 0)
            sum = (sum + step[i]) % MOD;
    return sum;
}

int main() {
    scanf("%lld %lld %lld", &l, &r, &k);
    // l 位数到 r 位数 = 数值在 [k^(l-1), k^r)；高位补零不改数位和，
    // 答案 = 恰好 r 位的合法个数 - 恰好 l-1 位的合法个数（l=1 时减去数值 0）
    ll ans = (count_good(r) - count_good(l - 1) % MOD + MOD) % MOD;
    printf("%lld\n", ans);
    return 0;
}

正文与代码的对应：step 就是系数向量 $c$（60 项推导式），conv 实现模 60 循环卷积（观察二），pow_dist 实现卷积快速幂（观察三），count_good(step, n) 计算 $G(n) = \sum_{i \in S} \mathrm{dist}_n[i]$（观察一），solve 末行完成区间相减。

复杂度

每次循环卷积 $60^2 = 3600$ 次乘加，快速幂 $\lceil \log_2 r \rceil \leqslant 60$ 层，求 $G(r)$、$G(l-1)$ 各一次：总时间 $O(60^2 \log r)$，空间 $O(60)$。与正解的 $60\times60$ 矩阵快速幂 $O(60^3 \log r)$ 同属 $\log$ 层的线性递推快速幂，这里借助循环矩阵结构把每层压到平方级，复杂度严格不弱于正解。实测 10 组真实数据每例 0.016–0.052s、峰值约 15MB，对 OJ 的 1s / 128MB 限制余量很大，Python 侧没有 TLE/MLE 风险。

总结

• 位数 → 数值区间：$k$ 进制 $n$ 位数即 $[k^{n-1}, k^n)$，所求区间是 $[k^{l-1}, k^r)$；补零不改变数位和，答案 $= G(r) - G(l-1)$。
• 状态压缩：判定只看数位和模 $\mathrm{lcm}(4,5,6) = 60$，状态从 $n(k-1)$ 级的精确和压到 60。
• 转移计数：数字按 $d \bmod 60$ 分类，$c_t = \lfloor k/60\rfloor + [t < k\%60]$，一步转移变成模 60 循环卷积。
• 快速幂：卷积的结合律 + 倍增跨过 $10^{18}$ 层；循环矩阵性质让每层只需 $O(60^2)$，总复杂度 $O(60^2 \log r)$。

图示解析

从题意到最终答案的推导路线，每一步消除上一步的一个瓶颈：

flowchart TD
    A["题意：k 进制 l~r 位中数位和被 4/5/6 整除的数"] --> B["区间转化：数值 in [k^(l-1), k^r)<br/>答案 = G(r) - G(l-1)"]
    B --> C["状态压缩：只需数位和 mod 60<br/>合法余数 28 个"]
    C --> D["转移计数：按 d mod 60 分类<br/>c_t = k//60 + [t < k%60]"]
    D --> E["线性递推：每层都是同一个循环卷积<br/>模 60 卷积，每层 O(60^2)"]
    E --> F["层数 1e18：卷积快速幂 O(60^2 log n)"]
    F --> G["G(n) = 合法余数分布求和<br/>输出 (G(r) - G(l-1)) mod 1e9+7"]

每个节点对应正文的一次瓶颈消除：区间转化解决"枚举数值不可行"，模 60 压缩解决"精确和状态爆炸"，余数计数解决"逐个枚举数字"，卷积快速幂解决"$10^{18}$ 层递推"。读图时按箭头顺序对照 ### 思路 的四个观察即可。