题目链接

其实我没写题解的习惯, 但是遇到了就写吧

Debug写了一个下午，写写题解纪念一下，顺便复习刚学的Floyd。本题解是针对初学Floyd的同学写的，请各位大佬忽略。

此题正解为DFS（n扩大到10^100000也不会超时）

原因：

Floyd的时间复杂度为O(n^3)，此处n为10(表示0-9每个数字)

DFS的理论时间复杂度为指数级，即O(2^k)，但本题中每个数字只搜索一次，重复的直接return，因此每一位实际的时间复杂度仅为O(n)

本题中注意整数n要用字符串读入，用long long会爆，用int128或高精度

代码(刚学int_128)

#include<bits/stdc++.h>
#define bigInt __uint128_t

using namespace std;

char a[39],k,x[19],y[19];
bool b[99];
int l,t;
bigInt s;
void out(bigInt x){ //int128输出要自己写
	if (x > 9) {
		out(x/10);
	}
	putchar(x%10+48);
}
void dfs(char c){ //深搜 
	if(b[c]) {
		return;//重复就退出
	} else {
		b[c]=1;
		for(int i=0;i<k;i++){
			if(x[i]==c){
				dfs(y[i]);
			}
		}
	}
}
int main(){
	scanf("%s%d",a,&k);
	l=strlen(a);
	for(int i=0;i<k;i++){
		cin>>x[i]>>y[i];
	}
	dfs(a[0]);
	b[0]=0;//先搜索最高位，因为最高位不能为0
	for(char i='1';i<='9';i++){
		t+=b[i],b[i]=0;
	}
	s = t;t = 0;
	for(int i=1;i<l;i++){//搜索其余位
		dfs(a[i]);
		for(char i='0';i<='9';i++){
			t+=b[i],b[i]=0;
		}
		s*=t,t=0;
	}
	out(s);
	return 0;
}

注: 此题解由巴黎世家编写, 懒馒头只提供int_128做法