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.