跳至正文

1 条题解

  • 0
    @ 2026-10-8 17:23:44

    【本题解由站长编写】

    对 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
    上传者