题解 | #恶魔果实#

题目描述

牛牛有一个正整数 （）和 个恶魔果实（）。每个果实提供一种能力：将数字 （）变为 （）。每种能力可无限次使用或不使用，且可能存在重复能力。问：对 的每一位独立应用这些变换后，最多能生成多少种不同的数字？答案对 取模。

本题是考察图的可达性分析 + 位掩码优化 + 独立位乘法原理的题，难度中等

核心思路

核心观察

• 位独立性：数字 的每一位变换互不影响，总方案数等于各位可选数字种类数的乘积。
• 变换闭包：由于能力可重复使用，若存在路径 ，则 可变为 。问题转化为求有向图中每个节点的可达集合大小。
• 图规模极小：节点仅为数字 （共 10 个），但输入边数 可达 ，需去重（邻接矩阵天然去重）。
• 高效表示：用位掩码（32 位整数）表示可达集合（第 位为 1 表示可变为数字 ），便于快速合并与计数。

算法步骤

1. 建图去重：
   • 初始化 邻接矩阵 graph。
   • 对每条输入边 ，置 graph[a][b] = 1（自动忽略重复边）。
2. 预处理可达集（BFS + 位掩码）：
   • 对每个数字 ：
     • 从 出发执行 BFS，遍历所有可达节点。
     • 用位掩码 res[i] 记录结果（访问节点 时，置 mask |= (1 << u)）。
3. 计算答案：
   • 将 转为字符串，逐位处理。
   • 对每位数字 ，用 __builtin_popcount(res[d]) 得到可选种类数。
   • 累乘所有位的种类数，每一步对 取模。

正确性分析

• 位独立性保证：变换仅作用于单个数字位，无跨位影响，乘法原理适用。
• BFS 完备性：BFS 遍历所有从起点 出发的可达节点（包括自身），位掩码完整记录集合。
• 去重正确性：邻接矩阵存储边，重复输入自动覆盖，不影响可达性。
• 边界处理：
  • 原始数字位 始终可达（BFS 起点包含自身）。
  • 无法变换的位（如无出边的 ）仅保留自身，种类数为 1。

复杂度分析

• 时间复杂度：
  • 建图：（，但实际仅 次有效赋值）。
  • BFS 预处理： 次 BFS，每次最多访问 个节点和 条边，总计 。
  • 答案计算：（ 最多 10 位）。
  • 整体为常数时间（因图规模固定为 10）。
• 空间复杂度：
  • 邻接矩阵： 个整数。
  • 位掩码数组： 个整数。
  • BFS 队列与访问数组：各 个元素。
  • 总空间为常数级。

参考代码

#include <bits/stdc++.h>
#include <unistd.h>
#include <sys/mman.h>
#include <sys/stat.h>
#define endl '\n'
#define int long long

namespace xss {
    class fast_istream {
    private:
        char* buf;
        char* end;
    public:
        fast_istream() {
            struct stat s;
            fstat(STDIN_FILENO, &s);
            buf = (char*)mmap(nullptr, s.st_size, PROT_READ, MAP_PRIVATE, STDIN_FILENO, 0);
            end = buf + s.st_size;
            setvbuf(stdout, nullptr, _IOFBF, 1 << 23);
        }
        template<typename T>
        typename std::enable_if<
            std::is_arithmetic<T>::value && !std::is_same<T, char>::value,
            fast_istream&
        >::type
        operator>>(T& x) {
            x = 0;
            bool neg = false;
            while (buf < end && (*buf == ' ' || *buf == '\n' || *buf == '\t' || *buf == '\r')) {
                ++buf;
            }
            if (buf >= end) return *this;
            if (*buf == '-') {
                neg = true;
                ++buf;
            } else if (*buf == '+') {
                ++buf;
            }
            while (buf < end && *buf >= '0' && *buf <= '9') {
                x = x * 10 + (*buf++ - '0');
            }
            if (neg) x = -x;
            return *this;
        }
        fast_istream& operator>>(char& c) {
            while (buf < end && (*buf == ' ' || *buf == '\n' || *buf == '\t' || *buf == '\r')) {
                ++buf;
            }
            if (buf < end) {
                c = *buf++;
            } else {
                c = '\0';
            }
            return *this;
        }
        fast_istream& operator>>(std::string& s) {
            s.clear();
            while (buf < end && (*buf == ' ' || *buf == '\n' || *buf == '\t' || *buf == '\r')) {
                ++buf;
            }
            while (buf < end && *buf != ' ' && *buf != '\n' && *buf != '\t' && *buf != '\r') {
                s += *buf++;
            }
            return *this;
        }

        explicit operator bool() const {
            return buf < end;
        }
    };

    class fast_ostream {
    public:
        template<typename T>
        typename std::enable_if<
            std::is_arithmetic<T>::value && !std::is_same<T, char>::value,
            fast_ostream&
        >::type
        operator<<(T x) {
            if (x < 0) {
                putchar_unlocked('-');
                x = -x;
            }
            if (x > 9) {
                (*this) << (x / 10);
            }
            putchar_unlocked(x % 10 + '0');
            return *this;
        }
        fast_ostream& operator<<(char c) {
            putchar_unlocked(c);
            return *this;
        }
        fast_ostream& operator<<(const char* s) {
            while (*s) putchar_unlocked(*s++);
            return *this;
        }
        fast_ostream& operator<<(const std::string& s) {
            for (char c : s) putchar_unlocked(c);
            return *this;
        }
    };

    fast_istream cin;
    fast_ostream cout;
}

#define cin xss::cin
#define cout xss::cout

using namespace std;

signed main() {
    string x;
    int  n, MOD = 1e4 + 7;
    cin >> x >> n;
    vector<vector<int>>graph(10, vector<int>(10));
    for (int i = 0; i < n; i++) {
        int u, v;
        cin >> u >> v;
        graph[u][v] = 1;
    }

    vector<int>res(10, -1);
    for (int i = 0; i < 10; i++) {
        int mask = 0;
        vector<bool>visited(10, false);
        queue<int>q;
        q.push(i);
        visited[i] = true;
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            if (res[u] != -1) {
                mask |= res[u];
                visited[u] = true;
                continue;
            }
            visited[u] = true;
            mask |= 1 << u;
            for (int j = 0; j < 10; j++) {
                if (!visited[j] && graph[u][j] == 1) {
                    visited[j] = true;
                    q.push(j);
                }
            }
        }
        res[i] = mask;
    }

    long long ans = 1;
    for (char c : x) {
        int d = c - '0';
        int cnt = __builtin_popcount(res[d]);
        ans = (ans * cnt) % MOD;
    }

    cout << ans << '\n';
    return 0;
}