「一本通 5.3 练习 3」恨 7 不成妻

形式化题目

定义一个正整数 $x$ 是与 $7$ 有关的，当且仅当满足以下三个条件之一：

$x$ 的十进制表示中包含数字 $7$ ；
$x$ 的各位数字之和是 $7$ 的整数倍（即 $\sum d_i \equiv 0 \pmod 7$ ）；
$x$ 本身是 $7$ 的整数倍（即 $x \equiv 0 \pmod 7$ ）。

若以上三个条件均不满足，则称 $x$ 与 $7$ 无关。

给定正整数区间 $[L, R]$ ，求区间内所有与 $7$ 无关的数字的平方和对 $10^9+7$ 取模的结果，即：

\left( \sum_{x \in [L, R], \, x \text{ 与 } 7 \text{ 无关}} x^2 \right) \bmod (10^9+7)

正解

思路

1. 前缀转化

区间 $[L, R]$ 上的平方和可以通过前缀和转化为计算 $[1, R]$ 和 $[1, L - 1]$ 的结果之差：

\text{Ans}(L, R) = (\text{calc}(R) - \text{calc}(L - 1)) \bmod (10^9+7)

2. 数位 DP 状态设计

由于判断一个数是否与 $7$ 无关，只需关注：

不填数字 $7$ ；
填完所有数位后的数模 $7$ 不为 $0$ ；
各位数字和模 $7$ 不为 $0$ 。

在从高位到低位填数的过程中，设当前位置为 $pos$ （从低到高编号 $0 \sim \text{len}-1$ ），前缀数值模 $7$ 为 $num\_mod$ ，前缀数位和模 $7$ 为 $sum\_mod$ 。记忆化状态可设计为三元组 $(pos, num\_mod, sum\_mod)$ 。

3. 平方和的展开与转移

数位 DP 的核心难点在于累加的不是个数，而是平方和。

假设当前位填入数字 $d$ （ $d \neq 7$ ），其贡献的实际权值为 $A = d \times 10^{pos}$ 。其后继子状态生成的合法后缀集合中，每个完整的合法后缀数值设为 $y_i$ 。则当前层拼出的完整数值为 $x_i = A + y_i$ 。

我们要维护后继状态返回的三个信息：

符合条件的数字总个数： $cnt = \sum 1$
符合条件的数字一次方和： $sum = \sum y_i$
符合条件的数字平方和： $sq = \sum y_i^2$

根据代数展开式：

\sum x_i^2 = \sum (A + y_i)^2 = \sum (A^2 + 2Ay_i + y_i^2) = A^2 \cdot cnt + 2A \sum y_i + \sum y_i^2

即：

\text{new\_sq} = A^2 \cdot cnt + 2A \cdot sum + sq

同理，一次方和的转移为：

\text{new\_sum} = \sum (A + y_i) = A \cdot cnt + sum

个数的转移为：

\text{new\_cnt} = cnt

因此，递归函数不仅需要返回合法国数个数，还需要同时返回这些数的一次和与平方和。转移时利用上述展开式向上合并即可。

代码

Python 版：

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
58
59
60
61
62
63#!/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-07-05 21:47
# update_at: 2026-07-05 21:47

from functools import cache
import sys

MOD = 10**9 + 7
POW10 = [pow(10, i, MOD) for i in range(21)]  # 10 的次幂模表


@cache
def dfs(pos: int, num_mod: int, sum_mod: int, is_limit: bool, digits: tuple[int, ...]) -> tuple[int, int, int]:
    """返回 (合法国数个数, 一次方和, 平方和) 模 MOD。"""
    if pos < 0:
        return (1, 0, 0) if num_mod != 0 and sum_mod != 0 else (0, 0, 0)

    limit = digits[pos] if is_limit else 9
    ans_cnt, ans_sum, ans_sq = 0, 0, 0

    for d in range(limit + 1):
        if d == 7:
            continue
        nxt_cnt, nxt_sum, nxt_sq = dfs(
            pos - 1,
            (num_mod * 10 + d) % 7,
            (sum_mod + d) % 7,
            is_limit and (d == limit),
            digits if is_limit and (d == limit) else (),
        )
        base = (d * POW10[pos]) % MOD
        base_sq = (base * base) % MOD

        ans_cnt = (ans_cnt + nxt_cnt) % MOD
        ans_sum = (ans_sum + nxt_sum + base * nxt_cnt) % MOD
        ans_sq = (ans_sq + nxt_sq + 2 * base * nxt_sum + base_sq * nxt_cnt) % MOD

    return (ans_cnt, ans_sum, ans_sq)


def count(n: int) -> int:
    """计算 [1, n] 内与 7 无关的数平方和。"""
    if n <= 0:
        return 0
    digits = tuple(int(c) for c in reversed(str(n)))
    return dfs(len(digits) - 1, 0, 0, True, digits)[2]


def solve() -> None:
    tokens = sys.stdin.read().split()
    if not tokens:
        return
    it = iter(tokens)
    t = int(next(it))
    out = [(count(int(r)) - count(int(l) - 1)) % MOD for l, r in ((next(it), next(it)) for _ in range(t))]
    sys.stdout.write("\n".join(map(str, out)) + "\n")


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118/**
 * 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-05 11:15
 * update_at: 2026-10-05 11:15
 */

// 数位 DP：求区间 [L, R] 内与 7 无关的数的平方和。
// 递归回溯时同时维护合法数字的个数、一次方和、平方和，
// 用完全平方公式 (base + y)^2 = base^2 + 2*base*y + y^2 逐位向上合并。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const ll MOD = 1000000007;

struct State {
    ll cnt; // 合法数字个数
    ll sum; // 合法数字之和
    ll sq;  // 合法数字平方和
};

ll pow10[20]; // pow10[i] = 10^i mod MOD

int digit[20]; // digit[i] = 上界 n 从高位起的第 i 位数字
int digit_len;

State memo[20][7][7]; // memo[pos][num_mod][sum_mod]：前缀不贴上限时的合并结果
char vis[20][7][7];   // 记忆化标记，只有 0/1，用 char 省内存

// pos: 当前要填从高位起的第 pos 位
// num_mod: 已填前缀数值模 7 的余数；sum_mod: 已填前缀数位和模 7 的余数
// limit: 已填前缀是否与上界 n 完全相同（贴上限时不能查表）
State dfs(int pos, int num_mod, int sum_mod, bool limit) {
    if (pos == digit_len) {
        // 所有位填完：数值模 7 和数位和模 7 都不为 0 才与 7 无关
        if (num_mod != 0 && sum_mod != 0) {
            State ok = {1, 0, 0};
            return ok;
        }
        State none = {0, 0, 0};
        return none;
    }

    if (!limit && vis[pos][num_mod][sum_mod]) {
        return memo[pos][num_mod][sum_mod];
    }

    int up = limit ? digit[pos] : 9;
    State ans = {0, 0, 0};
    for (int d = 0; d <= up; d++) {
        if (d == 7) {
            continue; // 数中出现了数字 7，整个数一定与 7 有关
        }
        State nxt = dfs(pos + 1, (num_mod * 10 + d) % 7, (sum_mod + d) % 7,
                        limit && (d == up));
        // 这一位实际贡献的权值 base = d * 10^(从低位起的位置)
        ll base = pow10[digit_len - 1 - pos] * d % MOD;
        ll base_sq = base * base % MOD;
        // 当前层拼出的完整数 x = base + y，对每个合法后缀 y 累加
        ans.cnt = (ans.cnt + nxt.cnt) % MOD;
        ans.sum = (ans.sum + nxt.sum + base * nxt.cnt) % MOD;
        ans.sq = (ans.sq + nxt.sq + 2 * base % MOD * nxt.sum + base_sq * nxt.cnt) % MOD;
    }

    if (!limit) {
        memo[pos][num_mod][sum_mod] = ans;
        vis[pos][num_mod][sum_mod] = 1;
    }
    return ans;
}

// 计算 [1, n] 中与 7 无关的数字平方和 mod MOD
ll calc(ll n) {
    if (n <= 0) {
        return 0;
    }
    digit_len = 0;
    ll x = n;
    while (x > 0) {
        digit[digit_len] = x % 10;
        digit_len++;
        x /= 10;
    }
    // 上面的 digit[] 是低位在前，翻转成高位在前
    for (int i = 0; i < digit_len / 2; i++) {
        int t = digit[i];
        digit[i] = digit[digit_len - 1 - i];
        digit[digit_len - 1 - i] = t;
    }
    // 每位权值依赖当前上界的长度，每次查询前清空记忆化表
    memset(vis, 0, sizeof(vis));
    return dfs(0, 0, 0, true).sq;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    pow10[0] = 1;
    for (int i = 1; i < 20; i++) {
        pow10[i] = pow10[i - 1] * 10 % MOD;
    }

    int t;
    cin >> t;
    for (int i = 0; i < t; i++) {
        ll l, r;
        cin >> l >> r;
        ll ans = (calc(r) - calc(l - 1) + MOD) % MOD;
        cout << ans << "\n";
    }

    return 0;
}

复杂度

时间复杂度：对于每个数位 DP 查询，状态数为位数 $\times 7 \times 7 \approx 19 \times 49 \approx 931$ 。每次转移枚举 $0 \sim 9$ 共 $10$ 种可能。单次查询运算量约在 $10^4$ 次以内，处理 $T \le 50$ 组数据耗时极低，总时间复杂度为 $O(T \cdot \log_{10} R \cdot 7^2)$ 。
空间复杂度：记忆化缓存大小与递归深度均为 $O(\log_{10} R \cdot 7^2)$ ，空间消耗仅数千状态，完全在内存限制内。

总结

本题是数位 DP 中经典的“高阶矩转移”题型。求解平方和时不能直接单独转移平方，必须同时维护零阶项（个数 $cnt$ ）与一阶项（数值和 $sum$ ），利用完全平方公式 $(A + y)^2 = A^2 + 2Ay + y^2$ 分拆出各项并在递归回溯时逐级累加。