洛谷

P1037 [NOIP2002 普及组] 产生数

题目描述

给出一个整数 nn 和 kk 个变换规则。

规则：

  • 一位数可变换成另一个一位数。
  • 规则的右部不能为零。

例如：n=234,k=2n=234,k=2。有以下两个规则：

  • 2⟶52\longrightarrow 5。
  • 3⟶63\longrightarrow 6。

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

  • 234234。
  • 534534。
  • 264264。
  • 564564。

共 44 种不同的产生数。

现在给出一个整数 nn 和 kk 个规则。求出经过任意次的变换（00 次或多次），能产生出多少个不同整数。

仅要求输出个数。

输入格式

第一行两个整数 n,kn,k，含义如题面所示。

接下来 kk 行，每行两个整数 xi,yix_i,y_i，表示每条规则。

输出格式

共一行，输出能生成的数字个数。

样例 #1

样例输入 #1

1
2
3
234 2
2 5
3 6

样例输出 #1

1
4

提示

对于 100%100\% 数据，满足 n<1030n \lt 10^{30}，k≤15k \le 15。

【题目来源】

NOIP 2002 普及组第三题

题目解析

刚开始看的时候还以为时用dfs遍历所有可能，但是一看n的范围就知道这不可行。

之后看了大佬题解（大佬不愧是大佬，思路非常之清晰且简易），发现这道题就是一个图的遍历搜索和高精度乘法，学到了很精妙的分析问题的方法，特此记录一下。

这道题目本质上是一个排列组合，求出每个数字能转换成其他多少种数字，之后对在该大数内的每个数字的转换种类数相乘即可。这时候就会发现求

首先是Floyd算法，这里不多赘述，自行搜索学习即可，这里是用Floyd算法来判断两点之间是否有通路，来看这个题的输入和描述，其实就是一个有向图的输入，从一个数字能到达另一个数字就相当于两点之间有单向通路。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//把每一个数字都当成中间节点
for(int k = 0; k <= 9; k++)
{
    //遍历起始点
    for(int i = 0; i <= 9; i++)
    {
        //尝试到达的点
        for(int j = 0; j <= 9; j++)
        {
            //如果能够到达就标记
            if(dis[i][j] || (dis[i][k]&&dis[k][j]))
                dis[i][j]=1;
        }
    }
}

之后由于数据过大，乘出来的数会爆longlong，高精度乘高精度又不会，但是仔细想一下发现可以写成高精度乘以低精度，之前在Acwing看的模板，直接贴上来：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//高精度乘低精度
// C = A * b, A >= 0, b >= 0
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;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back();

    return C;
}

之后就是一些细节问题了

  • Floyd自己到自己实际上是无效，改为0

    1
    2
    for(i=0;i<=9;i++)
    		dis[i][i]=0;

  • 高精度逆序输出

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include<iostream>
#include<string.h>
#include<vector>
using namespace std;
string n;
int dis[11][11]={0}, t[11];
vector<int> A;

void floyd()
{
	for(int k = 0; k <= 9; k++)
	{
		for(int i = 0; i <= 9; i++)
		{
			for(int j = 0; j <= 9; j++)
			{
				if(dis[i][j] || (dis[i][k]&&dis[k][j]))
				dis[i][j]=1;
			}
		}
	}
}

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;
	}
	while(C.back()==0&&C.size()>1) C.pop_back();
	return C;
}
int main()
{
	int k;
	cin >> n >> k;
	int len = n.length();
	int a,b;
	int i,j;
	for(i = 0; i < k; i++)
	{
		cin >> a >> b;
		dis[a][b]=1;
	}
	floyd();
	for(i=0;i<=9;i++)
		dis[i][i]=0;
	int time;
	for(i = 0; i <= 9; i++)
	{
		time = 1;
		for(j = 0; j <= 9; j++)
		{
			if(dis[i][j])
			time++;
		}
		t[i]=time;
	}
	
	A.push_back(1);
	for(i = 0; i < len; i++)
	{
		if(t[n[i]-'0'])
			A=mul(A,t[n[i]-'0']);
	}
	for(i = A.size()-1; i >= 0; i--)
	{
		cout << A[i];
	}
	return 0;
}