[NOIP2008-提高] 火柴棒等式

题目描述

给你 $n$ 根火柴棍（ $n \leqslant 24$ ），统计能拼出多少个形如 $A+B=C$ 的等式。 $A$ 、 $B$ 、 $C$ 是用火柴棍拼出的非负整数（非零数最高位不能是 $0$ ），加号与等号各需 2 根， $n$ 根火柴必须全部用完； $A \neq B$ 时 $A+B=C$ 与 $B+A=C$ 视为不同等式。数字 $0$ – $9$ 各需的火柴根数为： $0$ 要 6 根， $1$ 要 2 根， $2$ 要 5 根， $3$ 要 5 根， $4$ 要 4 根， $5$ 要 5 根， $6$ 要 6 根， $7$ 要 3 根， $8$ 要 7 根， $9$ 要 6 根。

输入格式：一个整数 $n$ 。

输出格式：一个整数，能拼成的不同等式的数目。

样例输入 1：14；样例输出 1：2（两个等式为 $0+1=1$ 和 $1+0=1$ ）。

样例输入 2：18；样例输出 2：9（如 $0+4=4$ 、 $0+11=11$ 、 $2+7=9$ 、 $10+1=11$ 等）。

思路

先查出每个数字需要的火柴根数，定义 $\mathrm{cost}(x)$ 为整数 $x$ 逐位求和的根数（ $\mathrm{cost}(0)=6$ ），扣除加号等号的 4 根后需满足 $\mathrm{cost}(A)+\mathrm{cost}(B)+\mathrm{cost}(A+B)=n-4$ 。由于 $C=A+B$ 被唯一确定，只需枚举有序对 $(A,B)$ 再 $O(1)$ 核对；又因为每位至少 2 根且 $C$ 的位数不小于 $A$ 、 $B$ ， $n \leqslant 24$ 时可证 $A$ 、 $B$ 都不超过 4 位，枚举到 $9999$ 即可。

参考代码

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#!/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 08:05
# update_at: 2026-10-02 08:05

import sys
from functools import cache

DIGIT_COST = (6, 2, 5, 5, 4, 5, 6, 3, 7, 6)  # 数字 0-9 各自所需火柴根数


@cache
def cost(x: int) -> int:
    """整数 x 拼成所需火柴根数（按十进制逐位查表，0 本身要 6 根）。"""
    total = 0
    while x:
        total += DIGIT_COST[x % 10]
        x //= 10
    return total or DIGIT_COST[0]


def count_equations(n: int) -> int:
    """数出恰好用完 n 根火柴的 A+B=C 等式个数，A、B 有序、全部火柴必须用完。"""
    k = n - 4  # “+”和“=”固定各占 2 根，剩下 k 根分给 A、B、C 三个数
    if k < 0:
        return 0

    # 关键观察：每位数字至少 2 根（1 最省），且 C=A+B 的位数不小于 A、B 的位数，
    # 所以 (位数A, 位数B) 必须满足 2*(位数A+位数B+max(位数A,位数B)) <= k；
    # 反解出单个数最多 (k-2)//4 位（n<=24 时为 4 位），按位数分桶后只枚举可行桶对。
    d_max = max((k - 2) // 4, 1)  # k < 6 时没有任何合法等式，留 1 位空跑即可
    groups: list[list[int]] = [[] for _ in range(d_max + 1)]
    for x in range(10 ** d_max):
        groups[len(str(x))].append(x)

    ans = 0
    for da in range(1, d_max + 1):
        for db in range(1, d_max + 1):
            if 2 * (da + db + max(da, db)) > k:
                continue  # 该位数组合的火柴下界已超预算，桶内不可能有解
            for a in groups[da]:
                ca = cost(a)
                if ca > k - 4:  # cost(B)、cost(C) 各至少还要 2 根
                    continue
                for b in groups[db]:
                    cb = cost(b)
                    if ca + cb <= k - 2:  # 剩余根数容得下 cost(C) 至少 2 根
                        ans += ca + cb + cost(a + b) == k  # 余额恰好等于 C 的根数
    return ans


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    print(count_equations(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/**
 * 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-06 14:16
 * update_at: 2026-10-06 14:16
 */
#include <cstdio>

typedef long long ll;

// 数字 0~9 各需要的火柴棍根数
const int DIGIT_COST[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};

ll n;      // 火柴棍总数
ll ans;    // 能拼出的等式数目

// 计算 x 逐位需要的火柴棍根数，特别地 cost(0) = 6
ll cost(ll x) {
    if (x == 0) return 6;
    ll sum = 0;
    while (x > 0) {
        sum += DIGIT_COST[x % 10];
        x /= 10;
    }
    return sum;
}

int main() {
    scanf("%lld", &n);
    ll k = n - 4; // 扣掉加号和等号共 4 根后，A、B、C 能用的火柴根数
    ans = 0;
    // C = A + B 被唯一确定，只需枚举 A、B，再 O(1) 核对 C 的根数
    // n <= 24 时 k <= 20，每位至少 2 根且 C 位数不小于 A、B，可证 A、B 均不超过 4 位
    for (ll a = 0; a <= 9999; ++a) {
        for (ll b = 0; b <= 9999; ++b) {
            if (cost(a) + cost(b) + cost(a + b) == k)
                ++ans;
        }
    }
    printf("%lld\n", ans);
    return 0;
}