题目描述
给出一个整数 n（n<10^30) 和 k 个变换规则（k<=15）。
规则：
一位数可变换成另一个一位数：
规则的右部不能为零。
例如：n=234。有规则（k＝2）：
2－>5
3－>6
上面的整数 234 经过变换后可能产生出的整数为（包括原数）:
234 534 264 564 共 4 种不同的产生数
问题：
给出一个整数 n 和 k 个规则。
求出：
经过任意次的变换（0次或多次），能产生出多少个不同整数。
仅要求输出个数。
输入输出格式
输入格式：
键盘输人，格式为：
n k x1 y1 x2 y2 … …
xn yn
输出格式：
屏幕输出，格式为：
一个整数（满足条件的个数）：
输入输出样例
输入样例#1：
234 2
2 5
3 6
输出样例#1：
4
这题我只实现了高精度+Floyd的做法。
现将每两个可以互相转换的数用数组存起来如：dis[x][y]=true
在进行Floyd，求出每一个数能转到的最多的数。
最后用高精度将每一种情况乘起来。
代码如下：
#include <iostream>
#include <string>
using namespace std;
string str;
int k,vis[10][10],f[10],num[101];
inline void floyd()
{
for (int k = 0;k <= 9;k++)
for (int i = 0;i <= 9;i++)
for (int j = 0;j <= 9;j++) vis[i][j] = vis[i][j] || (vis[i][k] && vis[k][j]);
}
int main ()
{
cin >> str >> k;
while (k--)
{
int a,b;
cin >> a >> b;
vis[a][b] = true;
}
for (int i = 0;i <= 9;i++) vis[i][i] = true;
floyd();
for (int i = 0;i <= 9;i++)
for (int j = 0;j <= 9;j++)
if (vis[i][j]) f[i]++;
int len = 2; num[1] = 1;
for (int i = 0;i < (int)str.length();i++) {
for (int j = 1;j <= 100;j++) num[j] *= f[str[i]-'0'];
for (int j = 1;j <= 100;j++)
if (num[j] >= 10) {
num[j+1] += num[j]/10;
num[j] %= 10;
}
while (num[len]) len++;
}
for (int i = len-1;i >= 1;i--) cout << num[i];
return 0;
}