【題目敘述】https://zerojudge.tw/ShowProblem?problemid=d844
【解題想法】Floyd-Warshall，大數乘法
- 這題很雷，WA了好幾次。
- 關鍵句「經過任意次的變換（0次或多次）」：
- 【例】如果規則中有 2－> 5 和 5－> 3，就算沒有直接給予 2－> 3 的規則，2－> 3 也要被視為合法的規則。
- 先定義 a[i][i] = 1 (本身也是一種存在)
- 利用Floyd-Warshall找出所有 a[i][j]， i－> j (0 <= i, j < 10) 的變換可能性。
- 計算changed[i] = sum(a[i][j]), 0 <= i, j < 10。
- 定義函式 times()：大數乘法 (因為答案可能高達10^30)。
#include <iostream>
#include <cstring>
using namespace std;
int ans[35] = {1};
int a[10][10], changes[10];
void times(int n){
int carry = 0;
for (int i = 0; i < 35; i++){
ans[i] *= n;
ans[i] += carry;
carry = ans[i] / 10;
ans[i] %= 10;
}
}
int main() {
int n, b, c, cnt;
string s;
memset(a, 0, sizeof(a));
for (int i = 0; i < 10; i++){
a[i][i] = 1;
}
cin >> s;
cin >> n;
for (int i = 0; i < n; i++){
cin >> b >> c;
a[b][ c] = 1;
}
for (int i = 0; i < 10; i++){
for (int j = 0; j < 10; j++){
for (int k = 0; k < 10; k++){
if (a[j][k] == 0){
if (a[j][i] == 1 && a[i][k] == 1){
a[j][k] = 1;
}
}
}
}
}
for (int i = 0; i < 10; i++){
cnt = 0;
for (int j = 0; j < 10; j++){
if (a[i][j] == 1) cnt++;
}
changes[i] = cnt;
}
for (int i = 0; i < s.length(); i++){
times(changes[s[i] - '0']);
}
bool flag = false;
for (int i = 34; i >= 0; i--){
if (ans[i] != 0) flag = true;
if (flag) cout << ans[i];
}
cout << "\n";
}