当前位置 博文首页 > ApocalypseTq的博客：P1037 [NOIP2002 普及组] 产生数 题解
此题正解为DFS（n扩大到10^100000也不会超时）
原因：
Floyd的时间复杂度为O(n^3)，此处n为10(表示0-9每个数字)
DFS的理论时间复杂度为指数级，即O(2^k)，但本题中每个数字只搜索一次，重复的直接return，因此每一位实际的时间复杂度仅为O(n)
本题中注意整数n要用字符串读入，用long long会爆，用int128
代码
#include<bits/stdc++.h>
#define lll __uint128_t
using namespace std;
char a[39],k,x[19],y[19];
bool b[99];
int l,t;
lll s;
void out(lll x){//int128输出要自己写
if(x>9)out(x/10);
putchar(x%10+48);
}
void dfs(char c){
if(b[c])return;//重复就退出
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);
}