产生数

题目描述

给定十进制整数 $n$ （ $n \leqslant 2000$ ）和 $k$ 条规则（ $k \leqslant 15$ ），每条规则形如 $x \to y$ （ $y \neq 0$ ）。一次变换：从 $n$ 的十进制表示中选一个数位，若该位数字等于某条规则的 $x$ ，可把它替换成对应的 $y$ 。求对 $n$ 施加 $0$ 次或多次变换，能得到的不同整数的个数（含 $n$ 本身）。

思路

把数字 $0 \sim 9$ 看成 $10$ 个节点，每条规则 $x \to y$ 是一条有向边。对每位数字求传递闭包 $R(d)$ （即该位能变成的所有数字集合），答案就是各位 $|R(s_i)|$ 的乘积。 $y \neq 0$ 保证不会出现前导零歧义。

参考代码

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#!/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-09-30 07:05
# update_at: 2026-10-04 11:09

import sys
from math import prod


def closure(rules: list[tuple[int, int]]) -> list[set[int]]:
    """每个数字经任意次变换能变成的数字集合（含自身，即传递闭包）。"""
    reach = [{d} | {y for x, y in rules if x == d} for d in range(10)]
    for mid in range(10):                  # Floyd 思想：枚举中转数字 mid
        for d in range(10):
            if mid in reach[d]:            # d → mid 成立，则 mid 能到的 d 也能到
                reach[d] |= reach[mid]
    return reach


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    n = next(data).decode()                # n 当字符串读，逐位独立统计
    k = int(next(data))                    # 变换规则条数
    rules = [(int(next(data)), int(next(data))) for _ in range(k)]

    reach = closure(rules)
    print(prod(len(reach[int(c)]) for c in 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/**
 * 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 12:00
 * update_at: 2026-10-05 12:00
 */

#include <iostream>
#include <string>
using namespace std;

typedef long long ll;

bool reach[10][10]; // reach[d][v] = 1 表示数字 d 经任意次变换能得到 v

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

    string n;
    int k;
    if (!(cin >> n)) return 0;
    cin >> k;

    // 初始化：每个数字能到达自身
    for (int d = 0; d < 10; ++d) reach[d][d] = true;

    for (int i = 0; i < k; ++i) {
        int x, y;
        cin >> x >> y;
        reach[x][y] = true; // 直接规则 x -> y
    }

    // Floyd 求传递闭包：10 个节点的有向图
    for (int mid = 0; mid < 10; ++mid)
        for (int d = 0; d < 10; ++d)
            if (reach[d][mid])
                for (int v = 0; v < 10; ++v)
                    if (reach[mid][v])
                        reach[d][v] = true;

    // 每位独立，乘法原理计数
    ll ans = 1;
    for (char c : n) {
        int d = c - '0';
        int cnt = 0;
        for (int v = 0; v < 10; ++v)
            if (reach[d][v]) ++cnt;
        ans *= cnt;
    }

    cout << ans << "\n";
    return 0;
}

目录

题目描述

思路

参考代码