侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 674 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

【DFS】产生数

GabrielxD
2023-09-25 / 0 评论 / 0 点赞 / 99 阅读 / 921 字
温馨提示:
本文最后更新于 2023-09-26,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

P1037 产生数


题目描述

给出一个整数 nnkk 个变换规则。

规则:

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

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

  • 252\longrightarrow 5
  • 363\longrightarrow 6

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

  • 234234
  • 534534
  • 264264
  • 564564

44 种不同的产生数。

现在给出一个整数 nnkk 个规则。求出经过任意次的变换(00 次或多次),能产生出多少个不同整数。

仅要求输出个数。

输入格式

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

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

输出格式

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

样例 #1

样例输入 #1

234 2
2 5
3 6

样例输出 #1

4

提示

对于 100%100\% 数据,满足 n<1030n \lt 10^{30}k15k \le 15

【题目来源】

NOIP 2002 普及组第三题

解题

方法一:DFS

思路

先看样例:规则 252\rightarrow 5 可以理解为 nn 中数位为 22 的位置有 2,52, 5 两个数可选,规则 363\rightarrow 6 可以理解为 nn 中数位为 33 的位置有 3,63, 6 两个数可选,那么能产生的整数就为:2×2×1=42 \times 2 \times 1 = 4

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

注意:最坏情况下答案会达到 103010^{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;
}

参考

0

评论区