1 条题解
-
0
【本题解由站长编写】
对 n 的每一位独立求可达数字集合(不是一个全局集合——这是本题最容易错的地方)。设 reach[d] 为数字 d 经若干次变换能得到的集合,初值只有 d 自己。规则可级联,重复扫描规则表松弛:若 d∈reach[a] 则把 b 并入 reach[d],直到没有变化。各位互不影响,答案是各位 |reach[d]| 的乘积。⚠️ 两个坑:① 必须逐位算而不是算一个全局可达集,否则
4会错误地借道2->3->5变成 3 种;② n 可达 30 位,答案远超 64 位(测试点 5 有 22 位),必须高精度——用 vector 低位在前存十进制位,重复乘小整数并进位。代码(C++17)
#include <bits/stdc++.h> using namespace std; // 高精度:十进制、低位在前,反复乘一个小整数 vector<int> mulSmall(vector<int> a, int b) { vector<int> res(a.size(), 0); long long carry = 0; for (size_t i = 0; i < a.size(); i++) { long long cur = (long long)a[i] * b + carry; res[i] = (int)(cur % 10); carry = cur / 10; } while (carry) { res.push_back((int)(carry % 10)); carry /= 10; } return res; } int reachSize[10]; int main() { string n; int k; cin >> n >> k; vector<pair<int, int>> rules(k); for (auto &r : rules) cin >> r.first >> r.second; // 每个数字独立求可达集:reach[d] 从 {d} 开始松弛 for (int d = 0; d < 10; d++) { bool has[10] = {false}; has[d] = true; for (int round = 0; round < 10; round++) { bool changed = false; for (auto &r : rules) { if (has[r.first] && !has[r.second]) { has[r.second] = true; changed = true; } } if (!changed) break; } int s = 0; for (int i = 0; i < 10; i++) if (has[i]) s++; reachSize[d] = s; } vector<int> ans(1, 1); for (size_t i = 0; i < n.size(); i++) { ans = mulSmall(ans, reachSize[n[i] - '0']); } for (int i = (int)ans.size() - 1; i >= 0; i--) cout << ans[i]; cout << "\n"; return 0; }
- 1
信息
- ID
- 4145
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 6
- 标签
- 递交数
- 2
- 已通过
- 0
- 上传者