产生数

题目描述

给出一个整数 n（n<10^30) 和 k 个变换规则（k<=15）。

规则：

一位数可变换成另一个一位数：

规则的右部不能为零。

例如：n=234。有规则（k＝2）：

2－>5

3－>6

上面的整数 234 经过变换后可能产生出的整数为（包括原数）:

234 534 264 564 共 4 种不同的产生数

问题：

给出一个整数 n 和 k 个规则。

求出：

经过任意次的变换（0次或多次），能产生出多少个不同整数。

仅要求输出个数。

输入输出格式

输入格式：

 

键盘输人，格式为：

n k x1 y1 x2 y2 ... ...

xn yn

 

输出格式：

 

屏幕输出，格式为：

一个整数（满足条件的个数）：

 

输入输出样例

输入样例#1： 234 2 2 5 3 6 输出样例#1： 4

思路：

这道题考查乘法原理，是数论中的一部分。可以把它想成是一个有向图，举个例子，如图所示，我们把0~9之间的整数列举出来，作为变化的模子。2可以变成自身，2-->23可以变成自身，3-->3；亦可以变成4，3-->4；由于4可以变成5，那么3变成4后也能变成5,3-->5另一个3同理4可以变成自身，4-->4；亦可以变成5,4-->5利用乘法原理，答案就是把所有点的出度乘起来，即1*3*3*2=18 /*codevs1009 产生数*/ #include<iostream> using namespace std; string n; int t,can[11][11]; int main() { cin>>n>>t; int x,y; while(t--){cin>>x>>y,can[x][y]=1;} for(int k=0;k<10;k++) for(int j=0;j<10;j++) for(int i=0;i<10;i++) if(i!=j&&j!=k&&i!=k) if(can[i][k]==1&&can[k][j]==1)can[i][j]=1; long long sum=1; for(int i=0;i<n.length();i++) { int n1=n[i]-'0',change=1; for(int j=0;j<10;j++) if(can[n1][j]==1&&n1!=j)change++; sum*=change; } cout<<sum; return 0; }