题解 | #恶魔果实#

问题分析

核心是对数字的每一位进行独立的状态转移计算：

1. 位独立性与组合爆炸：恶魔果实的能力作用于数字 的每一个独立位，而非整体数值。例如 ，规则 会产生 种结果。这本质上是一个组合数学中的乘法原理问题，总种类数为每一位可演变出的数字种类数的连乘积。
2. 规则的传递性与无限复用：如果存在规则 和 ，由于能力可无限次使用，必然隐含着 可以转变为 。这构成了一个连通性问题。
3. 有向性而非等价性：规则 并不意味着 。因此，状态转移图是一个有向图（Directed Graph），不能使用并查集（DSU）这类处理无向连通分量的数据结构。需要计算的是图的传递闭包（Transitive Closure）。

有向图传递闭包与乘法原理

针对上述分析，最优算法范式为 图论（可达性分析） + 组合数学。

将数字 视为图的 10 个顶点，将每一条转换规则 视为一条从节点 指向节点 的有向边。

1. 多源可达性分析 (Floyd-Warshall 算法变体)： 考虑到图的节点数绝对固定且极小（），求解某个数字最终能演变成哪些数字，等价于求有向图的传递闭包。使用基于布尔逻辑的 Floyd-Warshall 算法是最优雅的选择。该算法能够在 的恒定时间内，完美处理图中可能存在的环形规则（如 , ）和深层传递链（如 ）。
2. 乘法原理聚合： 得到所有 数字的传递闭包后（即预处理出任意数字 最终能演变出的数字集合大小 ），将给定的目标数字 拆解为单一字符。对于 的每一位数字 ，求所有 的乘积。

复杂度分析

• 时间复杂度：，其中 。

  • 读取 行规则并构建邻接矩阵：。
  • 求传递闭包（Floyd-Warshall）： 次基本操作，视为 常数时间。
  • 拆解数字 并计算连乘：，最多 位，视为 。

• 空间复杂度：。

  • 只需要维护一个 的二维布尔数组或整数矩阵用于存储连通关系。无需存储 条原始规则，内存占用几近于零。

代码实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

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

    int x, n;
    cin >> x >> n;

    array<array<bool, 10>, 10> graph{};
    for (int i = 0; i < 10; i++)
        graph[i][i] = true;

    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        graph[a][b] = true;
    }

    for (int k = 0; k <= 9; k++) {
        for (int i = 0; i <= 9; i++) {
            for (int j = 0; j <= 9; j++) {
                if (!graph[i][j] && graph[i][k] && graph[k][j]) {
                    graph[i][j] = true;
                }
            }
        }
    }

    array<int, 10> ways{};
    for (int i = 0; i <= 9; i++) {
        for (int j = 0; j <= 9; j++) {
            if (graph[i][j]) {
                ways[i]++;
            }
        }
    }

    ll total = 1LL;
    ll mod = 10007LL;
    string sx = to_string(x);
    for (const char c : sx) {
        int d = c - '0';
        total = (total * ways[d]) % mod;
    }
    cout << total << endl;
}