题目传送门 Floyd + 乘法原理 只需要将每个数字能够变换的次数累乘即可。 这道题需要用到 Floyd 计算每个数字最多能够变换的次数（能够连续变换）
数字只有十个，邻接矩阵就能存的下，使用 tran[i][i] 数组表示i,j两个数之间是否可以变换。
cpp
void floyd() {
for (int k = 0; k <= 9; k++)
for (int i = 0; i <= 9; i++)
for (int j = 0; j <= 9; j++)
if ((tran[i][k] && tran[k][j]) || (i == j)) //注意自己也要计数
tran[i][j] = true;
}此外结果范围会爆 long long，需要手写高精乘~~（从网上抄的板子)~~。
cpp
string mul(string x, int b) {
string result="";
int a[1000], c[1000], l , i, t, p = 0;
memset(a, 0, sizeof(a));
memset(c, 0, sizeof(c));
l = x.length();
for (i = l - 1; i >= 0; i--) a[l-i-1] = to_int(x[i]);
for (i = 0; i < l; i++) {
t = a[i] * b + c[i];
p = 0;
if (t >= 10) p = t / 10, t %= 10;
c[i] += t - c[i];
c[i + 1] += p;
}
if (p) l++;
for (i = l - 1; i >= 0; i--) result += to_char(c[i]);
return result;
}完整版代码
cpp
#include <bits/stdc++.h>
using namespace std;
string n;
string ans = "1";
int k, var[12];
bool tran[32][32];
int to_int(char c) {
return c - '0';
}
char to_char(int n) {
return n + '0';
}
void floyd() {
for (int k = 0; k <= 9; k++)
for (int i = 0; i <= 9; i++)
for (int j = 0; j <= 9; j++)
if ((tran[i][k] && tran[k][j]) || (i == j))
tran[i][j] = true;
}
void stat() {
memset(var, 0, sizeof(var));
for (int i = 0; i <= 9; i++) {
for (int j = 0; j <= 9; j++)
if (tran[i][j]) var[i]++;
}
}
string mul(string x, int b) {
string result="";
int a[1000], c[1000], l , i, t, p = 0;
memset(a, 0, sizeof(a));
memset(c, 0, sizeof(c));
l = x.length();
for (i = l - 1; i >= 0; i--) a[l-i-1] = to_int(x[i]);
for (i = 0; i < l; i++) {
t = a[i] * b + c[i];
p = 0;
if (t >= 10) p = t / 10, t %= 10;
c[i] += t - c[i];
c[i + 1] += p;
}
if (p) l++;
for (i = l - 1; i >= 0; i--) result += to_char(c[i]);
return result;
}
int main() {
cin >> n >> k;
for (int i = 1, n1, n2; i <= k; i++) {
cin >> n1 >> n2;
tran[n1][n2] = true;
}
floyd();
stat();
for (unsigned int i = 0; i < n.length(); i++)
ans = mul(ans, var[to_int(n[i])]);
cout << ans;
return 0;
}