【DFS】产生数

题目

P1037 产生数

---

题目描述

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

规则：

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

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

• $2\longrightarrow 5$。
• $3\longrightarrow 6$。

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

• $234$。
• $534$。
• $264$。
• $564$。

共 $4$ 种不同的产生数。

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

仅要求输出个数。

输入格式

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

接下来 $k$ 行，每行两个整数 $x_i,y_i$，表示每条规则。

输出格式

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

样例 #1

样例输入 #1

234 2
2 5
3 6

样例输出 #1

4

提示

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

【题目来源】

NOIP 2002 普及组第三题

解题

方法一：DFS

思路

先看样例：规则 $2\rightarrow 5$ 可以理解为 $n$ 中数位为 $2$ 的位置有 $2, 5$ 两个数可选，规则 $3\rightarrow 6$ 可以理解为 $n$ 中数位为 $3$ 的位置有 $3, 6$ 两个数可选，那么能产生的整数就为：$2 \times 2 \times 1 = 4$。

于是我们就可以把所有规则建成一个有向图，然后枚举 $0\dots 9$，对每个数跑一遍 DFS 求出其可以产生出的不同数的数量（注意：规则是可以传递的，比如有规则：$1\rightarrow 2, 2\rightarrow 3, 3\rightarrow 4$，那么我们就说数 $1$ 可以产生 4 个不同的数（$1,2,3,4$），数 $2$ 可以产生 3 个不同的数（$1,2,3$），以此类推…）（且传递的过程中可能会出现环，所以要记录已经传过的数，以免进入死循环）。最后枚举 $n$ 中每一位，并根据乘法原理把每一位数的产生数数量相乘即可得到答案。

注意：最坏情况下答案会达到 $10^{30}$，long long 是存不下的，可以使用高精度或在评测机有 64 位 g++/gcc 环境的情况下尝试 __int128。

代码

#include <cstdio>
#include <cstring>

using namespace std;

const int N = 35, M = 15;
char s[N];
int k;
int h[N], e[N], ne[N], idx;
bool vis[M];
int cnts[M];
__int128 ans = 1LL;

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

int dfs(int u) {
    vis[u] = true;
    int cnt = 1;
    for (int i = h[u]; ~i; i = ne[i]) {
        int v = e[i];
        if (!vis[v]) cnt += dfs(v);
    }
    return cnt;
}

void print(__int128 x) {
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) print(x / 10);
    putchar(x % 10 + '0');
}

int main() {
    scanf("%s%d", s, &k);
    memset(h, -1, sizeof(h));
    while (k--) {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
    }
    for (int i = 0; i < 10; ++i) {
        memset(vis, false, sizeof(vis));
        cnts[i] = dfs(i);
    }
    for (int i = 0; s[i]; ++i) ans *= cnts[s[i] - '0'];
    print(ans);

    return 0;
}

参考

• 哥们儿开学了，该学算法了
• 《ErikTse洛谷带刷100题》题单和题解