产生数
Time Limit: 1 Sec Memory Limit: 128 MB
给出一个整数 n(n<10^30) 和 k 个变换规则(k<=15)。
规则:
一位数可变换成另一个一位数:
规则的右部不能为零。
例如:n=234。有规则(k=2):
2-> 5
3-> 6
上面的整数 234 经过变换后可能产生出的整数为(包括原数):
234
534
264
564
共 4 种不同的产生数
问题:
给出一个整数 n 和 k 个规则。
求出:
经过任意次的变换(0次或多次),能产生出多少个不同整数。
仅要求输出个数。

传送门:SHUOJ1012

Input

键盘输人,格式为:   n k   x1 y1   x2 y2   ... ...   xn yn
## Output
屏幕输出,格式为: 一个整数(满足条件的个数):

Sample Input

1
2
3
234 2
2 5
3 6

Sample Output

1
4

题解

第一眼看是精度加dfs的题,然后dfs太久不写,不会写了想半天没想出来。。要好好学习啊- - 还好floyd记得比较牢,倒是一样可以做这道题 答案就是统计每一位能变换成的数字的乘积,如例子就是1*2*2=4,那么就可以画成floyd[10][10]
## AC code:(不包含输入类)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
import java.io.*;  
import java.math.BigInteger;
import java.util.*;
public class Main {
final static int MAX=9999999;
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
while(sc.hasNext()){
String s=sc.next();
int n=sc.nextInt();
int [][]floyd=new int[10][10];
for(int i=0;i<10;i++){
for(int j=0;j<10;j++){
if(i==j)
floyd[i][j]=0;
else
floyd[i][j]=MAX;
}
}
for(int i=1;i<=n;i++){
int a=sc.nextInt();
int b=sc.nextInt();
if(b!=0)
floyd[a][b]=0;
}
for(int k=0;k<10;k++){
for(int i=0;i<10;i++){
for(int j=0;j<10;j++){
if(floyd[i][j]>floyd[i][k]+floyd[k][j]){
floyd[i][j]=floyd[i][k]+floyd[k][j];
}
}
}
}
int[]jl=new int[10];
for(int i=0;i<10;i++){
for(int j=0;j<10;j++){
if(floyd[i][j]!=MAX){
jl[i]++;
}
}
}
BigInteger result=BigInteger.ONE;
for(int i=0;i<s.length();i++){
result=result.multiply(BigInteger.valueOf(jl[s.charAt(i)-'0']));
}
System.out.println(result);
}
}
}