牛客小白月赛26 I 恶魔果实

Description

牛牛得到了一堆神奇的恶魔果实，每个恶魔果实都给了牛牛一个改变数字的能力，可以把数字a变成数字b，现在牛牛有一个数字x，他想知道吃完这n个恶魔果实后，他可以把数字x变成多少种的数。
注：每一个恶魔果实的能力可以重复使用多次，当然也可以不用，存在相同能力的恶魔果实.

Solution

莫名其妙wa了很多次，一开始思路是直接dfs，每个数字变或不变，for找当前的数字能否到达1~9数字
然后tle了，考虑从图论的角度，可以用floyd处理出每个数字之间能否相互到达。
之后运用乘法原理，即每位数字能够有多少种情况，撑起来就可以啦。
不要忘记自己能到到达自己，对给自己连上一条边。

Code

#include<bits/stdc++.h>
typedef long long ll;
const int N = 1e6 + 5;
const int mod = 1e4 + 7;
using namespace std;
int maze[15][15];
int g[15][15];
ll vis[15];
string now;
int len;
int main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  int x, n;
  cin >> x >> n;
  while(x) {
    int tmp = x % 10;
    now += tmp + '0';
    x /= 10;
    maze[tmp][tmp] = 1;
    len++;
  }
  reverse(now.begin(), now.end());
  for(int i = 1; i <= n; i++) {
    int l, r;
    cin >> l >> r;
    maze[l][r]++;
  }
  for(int k = 0; k <= 9; k++) {
    for(int i = 0; i <= 9; i++) {
      for(int j = 0; j <= 9; j++) {
        maze[i][j] = maze[i][j] || (maze[i][k] && maze[k][j]);
      }
    }
  }
  for(int i = 0; i <= 9; i++) {
    for(int j = 0; j <= 9; j++) {
      if(maze[i][j]) {
        vis[i]++;
      }
    }
    //cout << i << ' ' << vis[i] << "\n";
  }
  ll ans = 1;
  for(int i = 0; i < now.size(); i++) {
    int p = now[i] - '0';
    ans *= (vis[p]);
    ans %= mod;
  }
  cout << ans << "\n";
  return 0;
}