[NOIP 2002 普及组] 产生数

题意

每一位数字可按规则变换任意次，求整个整数能产生多少种不同结果。

思路

十个数字上做传递闭包，reachable[d] 得到数字 d 最终可变成的集合。不同数位独立，根据乘法原理把每一位集合大小相乘。

Python 知识

每个数字集合只需一个整数位掩码。
bit_count() 直接求可达数字种数。
Python 大整数能直接保存最多 30 位数字产生的巨大答案。

代码

python

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


input = sys.stdin.buffer.readline
number, rule_count = input().split()
reachable = [1 << digit for digit in range(10)]
for _ in range(int(rule_count)):
    source, target = map(int, input().split())
    reachable[source] |= 1 << target
for middle in range(10):
    bit = 1 << middle
    for start in range(10):
        if reachable[start] & bit:
            reachable[start] |= reachable[middle]
answer = 1
for digit in number:
    answer *= reachable[digit - 48].bit_count()
print(answer)

原有 C++ 版本仍保留：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16/**
 * 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-17 01:40
 * update_at: 2026-07-17 01:40
 */
#include <bits/stdc++.h>
using namespace std;

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

    return 0;
}

复杂度

闭包是常数规模，扫描数字串 O(len(n))。

总结

每位独立选择时，先求单个符号的闭包，再用乘法原理组合。

[NOIP 2002 普及组] 产生数

目录

题意

思路

Python 知识

代码

复杂度

总结