https://www.luogu.org/problemnew/show/P1037

C++版本一

DFS

__int128,嘿嘿!!!

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
using namespace std;
typedef long long ll;
typedef __int128 lll;
const int N=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,q;
lll cnt;
int a;
string str;
vector<int>G[10];
int vis[50];
void dfs(int s){
    vis[s]=1;
    for(int j=0,k=G[s].size();j<k;j++){
        if(!vis[G[s][j]]){
            cnt++;
            dfs(G[s][j]);
        }
    }
}
inline void put(lll x)//快写
{
     if(x<0) putchar('-'),x=-x;
     if(x>9) put(x/10);
     putchar(x%10+'0');
}
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    cin>>str;
    scanf("%d",&k);
    for(int i=1;i<=k;i++){
        scanf("%d%d",&n,&m);
        G[n].push_back(m);
    }
    int len=str.size();
    lll ans=1;
    for(int i=0;i<=len;i++){
        cnt=1;
        memset(vis,0,sizeof(vis));
        if(i==0)
           vis[0]=1;
        dfs(str[i]-'0');
        if(i==0)
           vis[0]=0;
        ans*=cnt;
    }
    put(ans);
    //cout<<ans<<endl;
    //cout << "Hello world!" << endl;
    return 0;
}

 

C++版本二

最短路

#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;
}

Python版本一

var
  s:string;
  ch:char;
  p,i,j,k,x,y,n:longint;
  f:array[0..9]of longint;
  ans:array[0..101]of longint;
  a:array[0..9,0..9]of longint;

procedure init;//预处理
begin
  readln(s);
  p:=pos(' ',s);
  val(copy(s,p+1,length(s)-p),n);
  s:=copy(s,1,p-1);
  for i:=1 to n do
    begin
      readln(x,y);
      a[x,y]:=1;
    end;
  for k:=0 to 9 do
    for i:=0 to 9 do
      for j:=0 to 9 do
        if(i<>j)and(j<>k)and(k<>i)and(a[i,k]+a[k,j]=2)then a[i,j]:=1;//floyd算法
  for i:=0 to 9 do
    for j:=0 to 9 do
      f[i]:=f[i]+a[i,j];//统计每一位可转化数字的个数
end;

procedure times(x:longint);//高精度乘法
var
  i:longint;
begin
  for i:=1 to 100 do ans[i]:=ans[i]*x;
  for i:=1 to 100 do
    begin
      ans[i+1]:=ans[i+1]+ans[i] div 10;
      ans[i]:=ans[i] mod 10;
    end;
end;

procedure work;
begin
  ans[1]:=1;
  for i:=1 to length(s) do times(f[ord(s[i])-48]+1);//累乘
  k:=100;
  while ans[k]=0 do dec(k);//去除首位的0
  for i:=k downto 1 do write(ans[i]);
end;

begin
  init;
  work;
end.