[数据结构与算法]1920：【02NOIP普及组】产生数

• 我回来填坑啦
• 和简化版的最大差别就是数据范围，需要用高精度，也就是高精乘
• 这个代码我调了好久……最后发现函数里的“%”写成“/”了
• 错误如此低级啊……这题还是没什么难度的
• 一本通传送门和洛谷传送门

认真地写个分析

• 首先分析可以用什么算法
• 深搜、广搜、或者是图论
• 鉴于图论最简单（而且是Floyd）我就只写这一种了
• 那么就需要算出每个数字可能的所有变化
• 因为数字可能不只会变一次（例如1→2，2→3，就能得出1→3）
• 当然也可以用广搜完成这一步（不过Floyd最简单（大声））
• 接下来就是简单的排列组合题：已知每个数字有几种变化，求最后的组合数
• ——累乘就好
• 继续向下推进，可以知道数据范围较大，普通的long long肯定是过不去了
• 那么就要用高精乘，实际上是单精乘高精（超简单的）（就这我还错5555）
• 最后就只剩输出了，耶

#include<bits/stdc++.h>
using namespace std;
bool a[11][11];
long long f[11],k,s[110],ans,sum=1;
string n;
void cheng(int t){
	for(int i=1;i<=ans;i++) s[i]*=t;//乘
	for(int i=1;i<=ans;i++){//进位
		s[i+1]+=(s[i]/10);
		s[i]%=10;
	}
	while(s[ans+1]){//增加位数
		ans++;
		s[ans+1]+=(s[ans]/10);
		s[ans]%=10;
	}
}
int main()
{
	cin>>n>>k;
	for(int i=1;i<=k;i++){
		int x,y;
		cin>>x>>y;
		a[x][y]=1;
	}
	for(int i=0;i<=9;i++) a[i][i]=1;//自己变自己
	for(int k=0;k<=9;k++)//Floyd
		for(int i=0;i<=9;i++)
			for(int j=0;j<=9;j++)
				if(a[i][k]&&a[k][j])
					a[i][j]=1;
	for(int i=0;i<=9;i++) //统计每个数字的变化数量
		for(int j=0;j<=9;j++)
			if(a[i][j]) f[i]++;
	s[1]=1,ans=1;
	for(int i=0;i<n.size();i++)//累乘
		cheng(f[n[i]-'0']);	
	for(int i=ans;i>=1;i--)//输出
		cout<<s[i]; 
	cout<<endl;
	return 0;
}