首页 > 试题广场 >

恶魔果实

[编程题]恶魔果实

热度指数：1036 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

牛牛得到了一堆神奇的恶魔果实，每个恶魔果实都给了牛牛一个改变数字的能力，可以把数字a变成数字b，现在牛牛有一个数字x，他想知道吃完这n个恶魔果实后，他可以把数字x变成多少种的数。

注：每一个恶魔果实的能力可以重复使用多次，当然也可以不用，存在相同能力的恶魔果实.

输入描述:

第一行输入一个正整数x(1≤x≤10⁹)，和一个正整数n(1≤n≤10⁶),接下来n行，每行一个a(0≤a≤9 )和一个b(1≤b≤9)。

输出描述:

表示可以变的数字种类数，答案对10⁴+7取模

示例1

输入

输出

说明

456 556 656 466 566 666

示例2

输入

111 1
1 2

输出

说明

111 112 121 122 211 212 221 222

备注:

算法知识视频讲解

C++

kilomatutinal

这道题简单喵！

我们只需要知道：对于每个数字 0~9，它最终能变成哪些数字（包括它自己），然后把 x 的每一位的可能性乘起来，就得到总数喵！

用 to[a][b] 表示是否有直接能力把 a 变成 b 喵~
输入 n 条规则，就把对应的 to[a][b] 设为 true。

传递闭包（Floyd-Warshall）

因为能力可以重复使用，所以如果 a 能变成 c，c 能变成 b，那么 a 也能变成 b。
这就像朋友的朋友也是朋友一样喵~

我们用三层循环：

for (int k = 0; k < 10; k++)     // k 是中间人
    for (int i = 0; i < 10; i++)   // i 想交朋友
        for (int j = 0; j < 10; j++) // j 是目标
            if (to[i][k] && to[k][j])     // 如果 i 认识 k，k 认识 j
                to[i][j] = true;      // 那么 i 也认识 j 啦！

k 是中间人，i 想找 j，如果 i 认识 k，k 认识 j，那么 i 和 j 就也成为朋友啦！

这样循环完，to[i][j] 就表示 i 能不能通过任意次变换变成 j。

每个数字当然可以保持不变（不用果实），所以把 to[i][i] 也设为 true。

对于每个 i，数一数 to[i][j] 为 true 的 j 有多少个，存到 shu[i] 里。

把 x 的每一位拆出来，比如 x=123，就分别取 3,2,1（从低位到高位），
答案 = shu[3] * shu[2] * shu[1] % mod。
因为每一位独立选择，所以直接相乘喵~

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1e4 + 7;

int main() {
    ll x, n;
    cin >> x >> n;  // 输入数字 x 和果实个数 n
    vector<vector<bool>> to(10, vector<bool>(10, false)); 
    // 初始化邻接矩阵，一开始谁都不认识谁
    for (int i = 0; i < n; i++) 
    {
        int a, b;
        cin >> a >> b;
        to[a][b] = true;  // 记录直接能力：a 能变成 b
    }

    // 传递闭包（Floyd-Warshall）
    for (int k = 0; k < 10; k++)// k 是中间人
        for (int i = 0; i < 10; i++)// i 想交朋友
            for (int j = 0; j < 10; j++)// j 是目标
                if (to[i][k] && to[k][j])// 如果 i 认识 k，k 认识 j
                    to[i][j] = true;// 那么 i 也认识 j 啦！

    // 每个数字也能保持不变（自己变自己）
    for (int i = 0; i < 10; i++) to[i][i] = true;

    // 统计每个数字能变成多少种数字
    vector<int> shu(10);
    for (int i = 0; i < 10; i++) 
    {
        int cnt = 0;
        for (int j = 0; j < 10; j++)
            if (to[i][j]) cnt++;
        shu[i] = cnt;//比如数字 1 能变成 {1,3,5} 共3种
    }

    // 计算答案：把 x 的每一位乘起来
    ll ans = 1;
    while (x) {
        ans = ans * shu[x % 10] % mod;// 取最低位，乘上它的可能性，取模
        x /= 10;// 去掉最低位
    }
    cout << ans << '\n';  // 输出结果
}
/*
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣤⣤⡀⣀⣠⣤⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣀⡀⢀⣴⣾⣷⣶⣾⣿⣿⣿⣿⣿⣿⣿⣿⣷⣾⣿⣷⣦⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣾⣿⣿⣿⣿⣿⣿⣿⠿⠛⠛⠉⠉⠉⠉⠉⠉⠛⠻⠿⣿⣿⣿⣿⣿⣶⣤⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⢠⣾⣿⣿⣿⡿⠿⠛⠉⠉⠉⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠙⠿⣿⣿⣿⣷⣄⡀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⣀⣿⣿⣿⠟⠁⠀⠀⠀⠀⠀⠀⠀⣰⡆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⠿⣿⣿⣿⡄⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⣠⣾⣿⣿⠟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣶⣄⠀⠀⠀⠀⠀⢀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⣻⣿⣿⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⢹⣿⡿⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⣿⠁⠈⢢⡀⠀⠀⠀⢸⡇⢀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠻⣿⡟⠒⢦⡀⠀⠀⠀
⠀⠀⣠⣤⣤⣼⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠸⡇⠀⠀⠀⠉⢢⣄⠀⠀⢿⠊⠳⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⣷⡄⠀⢷⠀⠀⠀
⠀⢰⠇⠀⣰⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡇⠀⠀⠀⠀⡌⣹⠗⠦⣬⣇⠀⠉⢢⡀⠀⠀⠀⠀⠀⠀⠀⠀⠘⣿⡀⢸⡄⠀⠀
⠀⡟⠀⣼⣯⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⣆⢹⡀⠀⠀⠀⠉⠁⠀⠀⢀⣀⡁⠀⠀⠉⠳⢴⡆⠀⠀⠀⠀⠀⠀⢹⣧⠈⡇⠀⠀
⠀⡇⠀⠀⢻⣦⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣾⠻⠉⠛⠂⠀⠀⠀⠀⠀⠀⠻⠿⣿⣿⣿⣶⣦⡀⠛⣇⠀⠀⠀⠀⠀⣈⣿⠀⡇⠀⠀
⢸⡇⠀⠀⢠⣿⣷⣦⣀⡸⣷⣦⣶⡂⠉⠉⠉⢁⣤⣶⡶⠀⠀⠀⣀⣀⡴⠀⠀⠀⠀⠀⠀⠈⠉⠉⠁⠀⡟⢀⣴⣟⣰⣾⣿⣏⣠⠇⠀⠀
⠈⡇⠀⠀⢸⣿⠁⠉⣿⠛⠛⠃⡇⠀⠀⢠⣶⣿⡿⠛⠁⠀⠀⠉⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠼⢿⠟⠿⢿⡏⠀⠘⣿⡀⠀⠀⠀
⠀⢷⣀⣀⣿⠇⠀⠀⢿⡇⠀⢀⢱⡀⠀⠛⠛⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣼⠀⠀⢸⠇⠀⠀⢹⣿⣄⠀⠀
⠀⠀⣉⣿⡏⠀⠀⠀⠀⠀⠀⢸⣇⣳⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡰⣿⠃⠀⠀⠀⠀⠀⠀⣿⠈⢧⠀
⠀⠘⣿⣿⠁⠀⠀⠀⠀⠀⠀⠘⣿⡛⣶⠀⠀⣠⠔⠒⠛⠒⠦⡀⠀⠀⠀⠀⣠⡤⠶⠤⢤⣀⠀⠀⠀⢀⣏⡄⠀⠀⠀⠀⠀⡀⣿⡆⠈⣧
⣠⡾⠛⣿⣿⣧⠀⠀⠀⠀⢸⣿⠾⢿⡿⠀⣰⠃⠀⠀⠀⠀⠀⢹⡄⠀⠀⡼⠁⠀⠀⠀⠀⠈⠙⣦⠀⢸⣿⡇⣾⣣⡀⠀⢰⣿⣿⣿⣤⠾
⡟⠀⠀⠻⣿⡟⢷⡄⣤⡀⠈⣿⡀⣸⠇⠀⠏⠀⠀⠀⠀⠀⠀⠀⡇⠀⠀⡇⢀⡀⠀⠀⠀⠀⢀⡟⠀⠀⠋⣿⣿⣿⡇⣠⣿⠿⠛⢷⡀⠀
⠀⠀⠀⠀⣿⣇⣨⣿⣿⣿⣦⣽⣷⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠁⠀⠀⠃⠀⠙⠢⠤⠤⠴⢾⠀⠀⠀⠀⢸⣷⣿⣿⠟⠁⠀⠀⠈⣧⠀
⠀⠀⠀⠀⠈⠉⠉⠁⠈⠉⠈⢉⣿⡁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠀⠀⠀⠀⢸⡇⠀⠀⠀⠀⠀⠀⠀⣿⠀
*/

发表于 2026-03-02 01:20:55 回复(0)

C++

pandaC222

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define debug(x) cerr << #x << ": " << x << '\n';
const int INF = 0x3f3f3f3f3f3f3f3f;
const int mod=1e4+7;
//倒序不要忘记是--不是++
void solve(){
    int x,n;cin>>x>>n;
    vector<vector<int>> e(11);
    vector<vector<int>> is(11,vector<int>(11,0));
    while(n--){
        int a,b;cin>>a>>b;
        if(is[a][b]) continue;
        is[a][b]=1;
        e[a].push_back(b);
    }
    vector<int> cnt(11,0);
    for(int i=0;i<=9;i++){
        vector<bool> vis(10,false);
        queue<int> q;
        q.push(i);
        while(q.size()){
            cnt[i]++;
            vis[i]=1;
            int t=q.front();
            q.pop();
            for(auto u:e[t]){
                if(vis[u]) continue;
                vis[u]=1;
                q.push(u);
            }
        }
    }
    // for(int i=1;i<=9;i++) cout<<cnt[i]<<" ";
    // cout<<"\n";
    int ans=1;
    while(x){
        int cur=x%10;
        ans=ans*cnt[cur]%mod;
        x/=10;
    }
    cout<<ans;
}
signed main(){
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t = 1;
    // cin>>t;
    while(t--){
        solve();
    }return 0;
}

发表于 2026-03-02 20:16:05 回复(0)

提交观点

问题信息

难度：

2条回答 12收藏 11浏览

恶魔果实

输入描述:

输出描述:

输入

输出

说明

输入

输出

说明

备注:

传递闭包（Floyd-Warshall）

问题信息

热门推荐

相关试题