对十个数字求变换传递闭包，再把每一位的可达数字数相乘。
OJ: luogu
题目 ID: P1037
难度:普及-
题意
每一位数字可按规则变换任意次，求整个整数能产生多少种不同结果。
思路
十个数字上做传递闭包，reachable[d] 得到数字 d 最终可变成的集合。不同数位独立，根据乘法原理把每一位集合大小相乘。
Python 知识
- 每个数字集合只需一个整数位掩码。
bit_count()直接求可达数字种数。- Python 大整数能直接保存最多 30 位数字产生的巨大答案。
代码
位掩码 + 传递闭包（Python 主解）
把 reachable[d] 压成一个 10 位掩码，用 Floyd 的三重循环求闭包：中点必须是最外层循环，start 能到 middle 时把 middle 的掩码整个并入。
python
import 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:
# bit_count() 求该位数字可达的种数
answer *= reachable[digit - 48].bit_count()
print(answer)位掩码 + 传递闭包（C++）
思路与 Python 主解完全一致，只是用 long long 的低 10 位当掩码，__builtin_popcountll 数可达数字种数。答案最大约 long long，所以用 __int128 保存并手写输出。
cpp
/**
* 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-10-18 19:44
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
string number; // 原整数 n，最多 30 位，按字符串读
ll rule_count; // 变换规则条数
// reachable[d] 是位掩码：第 b 位为 1 表示数字 d 能变成数字 b
ll reachable[10];
// 答案最大约 10^30，超过 long long，用 __int128 保存并自己输出
void print_i128(__int128 value) {
if (value == 0) {
cout << 0 << '\n';
return;
}
string digits;
while (value > 0) {
char ch = '0' + value % 10;
digits.push_back(ch);
value /= 10;
}
reverse(digits.begin(), digits.end());
cout << digits << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> number >> rule_count;
// 每个数字至少能变成自己
for (int digit = 0; digit < 10; digit++) {
reachable[digit] = 1LL << digit;
}
for (ll i = 0; i < rule_count; i++) {
ll source, target;
cin >> source >> target;
reachable[source] |= 1LL << target; // 走一步
}
// Floyd 传递闭包：中转数字 middle 必须在最外层
for (int middle = 0; middle < 10; middle++) {
ll middle_bit = 1LL << middle;
for (int start = 0; start < 10; start++) {
// start 能变成 middle，就把 middle 能变成的数字一并并入
if (reachable[start] & middle_bit) {
reachable[start] |= reachable[middle];
}
}
}
// 各数位互不影响，按乘法原理把每位可取的数字种数相乘
__int128 answer = 1;
for (char ch : number) {
int digit = ch - '0';
int kinds = __builtin_popcountll(reachable[digit]);
answer *= kinds;
}
print_i128(answer);
return 0;
}集合 + DFS（Python 替代写法）
也可以不做闭包，直接对每个数字从它自己出发 DFS：nSet[d] 收集 d 在图上能走到的全部数字。dfs 靠集合做访问标记，因此环不会无限递归。这个写法更直白地表达“任意次变换”，代价是要真的存 10 个集合。
python
import sys
type Graph = list[list[int]]
# dfs 遍历 u 能到达的点
def dfs(g:Graph,u:int ,s:set):
if u in s:
return
s.add(u)
for v in g[u]:
dfs(g,v,s)
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
n = next(data) # 0 <= n < 31，单个整数
k = next(data)
# build graph
g:Graph = [[] for _ in range(10+1)]
for _ in range(k):
u = next(data) # x >= 0
v = next(data) # y < n
g[u].append(v)
nSet:list[set] = [set() for _ in range(10)]
# nSet 记录每个数字可以到达的数字的集合
for i in range(10):
dfs(g,i,nSet[i])
ans = 1
for c in str(n):
# 有 len 种可能的变化
ans *= len(nSet[int(c)])
print(ans)
if __name__ == "__main__":
solve()复杂度
闭包是常数规模，扫描数字串 O(len(n))；DFS 写法的图只有 10 个点和至多 15 条边，O(10 + k) 预处理后可 O(len(n)) 回答。
总结
每位独立选择时，先求单个符号的闭包，再用乘法原理组合。