[NOIP2002 普及组] 产生数

题目描述

给出一个整数

n

n

n 和

k

k

k 个变换规则。

规则：

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

例如：

n

=

234

,

k

=

2

n=234,k=2

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

• $2⟶5$
• $3⟶6$

上面的整数

234

234

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

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

共

4
服务器托管网

4

4 种不同的产生数。

现在给出一个整数

n

n

n 和

k

k

k 个规则。求出经过任意次的变换（

0

0

0 次或多次），能产生出多少个不同整数。

仅要求输出个数。

输入格式

第一行两个整数

n

,

k

n,k

n,k，含义如题面所示。

接下来

k

k

k 行，每行两个整数

x

i

,

y

i

x_i,y_i

xi​,yi​，表示每条规则。

输出格式

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

样例 #1

样例输入 #1

234 2
2 5
3 6

样例输出 #1

4

提示

对于

100

%

100%

100% 数据，满足

n

n1030，

k

≤

15

k le 15

k≤15。

【题目来源】

NOIP 2002 普及组第三题

---

思路

每个数字作为图中的一个节点，将每个数字可以到达的后继数字连成一条有向边，形成一个有向图。

先用深度优先搜索计算每个数字能够到达的节点数，然后根据数字字符串中每个数字能够到达的节点数，利用排列组合计算求出经过任意次的变换（

0

0

0 次或多次），能产生出不同整数的个数。

因为方案数可能非常大，用__int128 类型用于存储方案数。write 函数用于输出 __int128 类型的整数。

---

AC代码

#include 
#include 
#include 
#define ll long long
#define lll __int128
#define AUTHOR "HEX9CF"
using namespace std;

const int N = 15;

listint> v[N];
bitsetN> vis;
int cnt[N];

void dfs(int x)
{
    vis[x] = 1;
    for (const auto &i : v[x])
    {
        if (!vis[i])
        {
            dfs(i);
        }
    }
}

void write(lll x)
{
    if (x / 10)
    {
        write(x / 10);
    }
    putchar(x % 10 + '0');
}

int main()
{
    string n;
    int k;
    lll ans;
    ans = 1;
    cin >> n >> k;
    for (int i = 0; i  k; i++)
    {
        int a, b;
        cin >> a >> b;
        v[a].push_front(b);
    }
    for (int i = 0; i  10; i++)
    {
        vis.reset();
        dfs(i);
        cnt[i] = vis.count();
        // cout 
    }
    for (const auto &i : n)
    {
        // cout 
        ans *= cnt[i - '0'];
    }
    // cout 
    write(ans);
    return 0;
}

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net

相关推荐: Android系统启动流程概览
第一节 Android系统启动流程
第二节 init.rc 解析
第三节 Zygote进程的启动过程
第四节 SystemServer 启动流程
第五节 其他小点

目录 第一节 Android系统启动流程 init进程 第二节 init.rc 解析 第三节 Zygote进程的启动过程 3.1 AndroidRuntime.start 做了三件事： 3.1.1 startVm： 3.1.2 startReg： 3.1.2.…