产生数 题解

这个题是一个排列组合问题，

以这样一组数据为例：
12040 7
1 2
1 3
4 1
2 5
5 3
4 6
6 0
1可以变成2、3，2又可以变成5，共有1（不变）、2、3、5四个可能数字；
同理，2有2、5、3三个可能数字。
3不能变成其他数字，只有一个可能数字。
4可以变成4、1、2、3、5五个可能数字。
5可以变成5、3两个可能数字。
6不能变成其他数字，只有一个可能数字。
0可以变成0、6两个可能数字。
在12040这个数字中，每个数码都可能变为对应的可能数字，根据乘法原理，共有4×3×2×5×2=240种可能数字，并且不会重复。

因此我们可以递归搜索输入数字的每一位，用一个数组来存每一位可以变换的种类，然后用循环将所有种类相乘。用for循环对每一位进行dfs搜索，而在dfs搜索中，要循环1~9，看是否可以变换。注意：可以变换的种类中要加上自己本身。
以下是我的第一版代码：

#include<bits/stdc++.h>
using namespace std;

string str;//用字符串输入
int k;//输入题目中的k种变换
int m[20];//用来存某个数字可以变到另一个数字，表示从m[i]变化到n[i]
bool vis[20];//标记某个数字是否用过
int t[5000];//存str中每个数字的变换种类
int ans,res=1;//res是最终结果

void dfs(int s){
	for(int i=0;i<k;i++){//遍历输入的k种情况
		if(m[i]==s&&!vis[n[i]]){//如果s是m[i]，那就去找对应的n[i]
			ans++;
			vis[n[i]]=true;
			dfs(n[i]);
		}
	}
}

int main(){
	cin>>str>>k;
	for(int i=0,a,b;i<k;i++){
		cin>>a>>b;
		m[a]=b;//表示：可以从a变到b
	}

	int len=str.size();
	for(int i=0;i<len;i++){//遍历每一个数字
		ans=0;//将ans重置为0
		int c=str[i]-'0';//取出对应的数字
		memset(vis,false,sizeof vis);//每次都要把vis数组重置为false
		vis[c]=true;//标记这个数字遍历过
		dfs(c);
		t[i]=1+ans;//ans是当前数字可以有多少种变换结果，还要加上它本身，所以加一
	}
	
	for(int i=0;i<len;i++){//将所有情况相乘
		res*=t[i];
	}
	cout<<res;
	return 0;
} 

但这个代码是不通过的，因为题目中的数字范围较大，必须用高精度乘法，将每一个数字的情况相乘。
高精度乘法详解。

更改后的代码

#include<bits/stdc++.h>
using namespace std;

string str;
int k;
int m[20],n[20];//用来存某个数字可以变到另一个数字，表示从m[i]变化到n[i]
bool vis[20];
int t[5000];//存str中每个数字的变换种类
int ans;

void dfs(int s){
	for(int i=0;i<k;i++){
		if(m[i]==s&&!vis[n[i]]){
			ans++;
			vis[n[i]]=true;
			dfs(n[i]);
		}
	}
}

//高精度:计算A和b的乘积
vector<int> mul(vector<int> &A,int b){
  vector<int> C;
  int t=0;
  for(int i=0;i<A.size()||t;i++){
    if(i<A.size()) t+=A[i]*b;
    C.push_back(t%10);
    t/=10;
  }
  return C;
}


int main(){
	cin>>str>>k;
	for(int i=0,a,b;i<k;i++){
		cin>>a>>b;
		m[i]=a,n[i]=b;//建立可到达的对应关系
	}

	int len=str.size();
	for(int i=0;i<len;i++){//这里是搜索str中的每一个数，所以要ans重置为0，vis也要重置
		ans=0;
		int c=str[i]-'0';
		memset(vis,false,sizeof vis);
		vis[c]=true;//标记str中的某一位已走过
		dfs(c);
		t[i]=1+ans;//还要加上它本身，所以加一
	}
	
	//高精度计算
	vector<int> C;//C是最终答案
	C.push_back(t[0]);//先将t[0]作为第一个参数，即一个数组。直接传入即可，不需要把它转换成数组
//	while(t[0]){
//		C.push_back(t[0]%10);
//		t[0]/=10;
//	}
	
	for(int i=1;i<len;i++){
		C=mul(C,t[i]);
	}
	for(int i=C.size()-1;i>=0;i--){
		cout<<C[i];
	}
	return 0;
} 

方法二：

这道题是排列组合的乘法原理，但是每一位都有多少种可能呢，其实可以把这个问题转换成当前这位数字与多少个数字联通，这里处理是否联通用的是一种方法——Floyd变形

Floyd模板

初始化:

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            if (i == j) d[i][j] = 0;
            else d[i][j] = INF;

// 算法结束后，d[a][b]表示a到b的最短距离
void floyd()
{
    for (int k = 1; k <= n; k ++ )
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

这里将模板变形，将联通视为1，不连通视为0。
d[i][j] 表示从点 i 到点 j 是否联通。

for (k = 1; k <= n; k++)
  for (i = 1; i <= n; i++)
    for (j = 1; j <= n; j++)
　　  dis[i][j] = dis[i][j] || (dis[i][k] && dis[k][j]);
　　  //如果点i到点k连通，并且点k到点j连通，那么点i到点j连通，所以dis[i][j]=1

AC代码

#include<bits/stdc++.h>
using namespace std;

string str;
int k;
int dis[20][20];//记录点i到点j的连通关系，1为连通，0为不连通
bool vis[20];
int t[5000],num[20];//num数组表示数字0~9的每个数字的可变换种类，t数组表示str中每个数字的变换种类
int ans;

//高精度乘法
vector<int> mul(vector<int> &A,int b){
  vector<int> C;
  int t=0;
  for(int i=0;i<A.size()||t;i++){
    if(i<A.size()) t+=A[i]*b;
    C.push_back(t%10);
    t/=10;
  }
  return C;
}


int main(){
	cin>>str>>k;
	for(int i=0,a,b;i<k;i++){
		cin>>a>>b;
		dis[a][b]=1;//将点a到点b设为连通
	}

	int len=str.size();
	//floyd!!!!，这里先用flody将每个点的连通关系找到
	for(int k=1;k<=9;k++){
		for(int i=0;i<=9;i++){
			for(int j=0;j<=9;j++){
			 //如果点i到点k连通，并且点k到点j连通，那么点i到点j连通，所以dis[i][j]=1
				if(dis[i][k]&&dis[k][j])
					dis[i][j]=1;
			}
		}
	}
	for(int i=0;i<=9;i++){//算出数字0~9每个数字的连通数有多少
		dis[i][i]=1;//它自己到自己也是一种连通
		for(int j=0;j<=9;j++){
			if(dis[i][j])
				num[i]++;//如果点i到点j连通，那么num[i]的种类+1
				//这里的num[0]就是数字0的连通数，num[1]就是数字1的连通数
		}
	}
	
	for(int i=0;i<len;i++){//算出str中每个数字的连通数
		t[i]=num[str[i]-'0'];//str[i]-'0'表示它是数字几，而num[str[i]-'0']表示该数值的数字的连通数
	}
	
	//高精度计算
	vector<int> C;
	C.push_back(t[0]);
//	while(t[0]){
//		C.push_back(t[0]%10);
//		t[0]/=10;
//	}
	
	for(int i=1;i<len;i++){
		C=mul(C,t[i]);
	}
	for(int i=C.size()-1;i>=0;i--){
		cout<<C[i];
	}
	return 0;
}