luogu p1037 产生数双做法

//图论做法+高精
#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 (){
  ios::sync_with_stdio(false);
  cin >> str >> k;
  while (k--) {
    int a,b;
    cin >> a >> b;
    vis[a][b] = true;  //a可以变成b
  }
  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]++;  //求出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;
}