产生数

题目

产生数

---

解析

利用乘法原理，得到将每一位能拓展到的个数相乘即可
这题有一些注意点：
1：用字符串输入n
2：开高精(int128好像也能卡过去，longlong应该不行)
3：没了Floyd记得a[i][i]=1

code:

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int k,x,y,t[10],s[101],r=100,tot=0;
string n;
bool a[10][10];
void mul(int sk)
{
	for(int i=1;i<=r;i++)s[i]*=sk;
	for(int i=1;i<=r;i++)s[i+1]+=s[i]/10,s[i]%=10;
}
int main()
{
	s[1]=1;
	cin>>n;
	scanf("%d",&k);
	while(k--)scanf("%d%d",&x,&y),a[x][y]=1;
	for(int i=0;i<=9;i++)a[i][i]=1;
	for(int k=0;k<=9;k++)for(int i=0;i<=9;i++)for(int j=0;j<=9;j++)a[i][j]=a[i][j]||(a[i][k]&&a[k][j]);//Floyd传递闭包
	for(int i=0;i<=9;i++)for(int j=0;j<=9;j++)if(a[i][j])t[i]++;//累加
	while(tot<n.size())
	{
		mul(t[(n[tot++]-'0')%10]);//高精乘
	}
	while(s[r]==0)r--;
	while(r)printf("%d",s[r--]);//输出
	return 0;
}