[NOIP2002-普及] 产生数

题目描述

给定整数 $n$ （ $n < 10^{30}$ ）和 $k$ （ $k \leqslant 15$ ）条一位数变换规则 $x \to y$ （ $y \neq 0$ ）。可对 $n$ 的任意一位做任意次（含 0 次）变换，求能产生的不同整数个数（含 $n$ 本身）。输入：第一行 n k，接下来 $k$ 行每行一条规则 x y；输出：一个整数。样例：输入 234 2、规则 2 5、3 6 时输出 4（234、534、264、564）。

思路

把数字 $0 \sim 9$ 看成图上结点，规则 $x \to y$ 是有向边，"数字 $d$ 经任意次变换能变成的数字集合"就是从 $d$ 出发的可达点集（含自身），用位集 Floyd 求传递闭包。每位数字 $d$ 有 $\mathrm{popcount}(g[d])$ 种取值，各位独立，由乘法原理答案为所有位的可达个数之积。答案可达 $10^{30}$ 量级，超出 64 位整数，用 unsigned __int128 计算。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18import sys
from functools import reduce
from operator import mul

# g[d]：位集，d 经任意次变换能到达的数字个数（含 d 自身）
g = [1 << d for d in range(10)]
data = iter(sys.stdin.buffer.read().split())  # 全部读入后用 next() 顺序消费（兼容 \r\n 行尾）
n = next(data).decode()  # n 最多 30 位，要逐位访问，按字符串读
k = int(next(data))
for i in range(k):
    x, y = int(next(data)), int(next(data))
    g[x] |= 1 << y
for m in range(10):  # Floyd 传递闭包：若 i->j 且 j 可达 d，则 i 可达 d
    for i in range(10):
        if g[i] >> m & 1:
            g[i] |= g[m]
# 答案 = 每一位可选数字个数之积（n 最大 30 位，乘积用 Python 大整数）
print(reduce(mul, (bin(g[int(c)]).count('1') for c in n)))

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/**
 * 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 12:40
 * update_at: 2026-10-06 12:41
 */
#include <cstdio>
#include <string>
#include <iostream>

typedef long long ll;

// g[d]：位集，第 e 位为 1 表示数字 d 经任意次变换能变成数字 e（初始含自身，允许 0 次变换）
ll g[10];
// s：数字 n（最多 30 位），按字符串逐位访问；k：规则条数
std::string s;
ll k;

int main() {
    std::cin >> s >> k;
    for (ll d = 0; d < 10; d++) g[d] = (ll)1 << d; // 初始 g[d] 只含 d 自己
    for (ll i = 1; i <= k; i++) {
        ll x, y;
        std::cin >> x >> y;   // 规则 x -> y，加入一条有向边
        g[x] |= (ll)1 << y;
    }
    // Floyd 求传递闭包：若 i 能到 m 且 m 能到 e，则 i 能到 e
    for (ll m = 0; m < 10; m++)
        for (ll i = 0; i < 10; i++)
            if (g[i] >> m & 1) g[i] |= g[m];
    // 每一位数字 d 有 popcount(g[d]) 种取值，各位独立，由乘法原理连乘
    // n 最多 30 位、每位最多 10 种，答案可达 10^30，超出 ll，用 unsigned __int128 输出
    unsigned __int128 ans = 1;
    for (ll i = 0; i < (ll)s.size(); i++) ans *= __builtin_popcountll(g[s[i] - '0']);
    // __int128 无法直接用 cout 输出，转成十进制字符串打印
    std::string out;
    do {
        out += char('0' + (int)(ans % 10));
        ans /= 10;
    } while (ans > 0);
    for (ll i = (ll)out.size() - 1; i >= 0; i--) putchar(out[i]);
    putchar('\n');
    return 0;
}

[NOIP2002-普及] 产生数

目录

题目描述

思路

参考代码