P1037 [NOIP2002 普及组] 产生数 python 题解

原题链接：产生数

原理解释

本题就是基本的dfs，对每一个数遍历深搜，得到他能变化的所有情况，最后相乘就是结果，网上都是c的解法，需要用到高精度，但是python可以处理大数，不需要。

vis[]判断该数是否变换过，防止重复

以 n=123 ,k=2，变换列表x=[1,3] ,y=[3,4] ,即1->3 ,3->4:

先遍历1：遍历整个x y, vis[y[i]] != 0 and x[i]==1 代表1可以变成y[i],就是3

​ 然后继续，4没有遍历过，且x[i]==3 所以3变成4，遍历完，退出。

​ 变换了2次，加上自身就是一种就是3次。

更新vis

在遍历2： 遍历x ,y. 没有x[i]==2,退出

更新vis

遍历3: 1->3 不匹配，下一个 ，3->4, x[i]==3,且vis[4]没有使用过，加一，然后退出，加上自身就是一种就是2次。

最后结果就是2*3=6次，次数用t保存即可

AC代码：

def dfs(e):
    global ans
    for i in range(1, k + 1):
        if not vis[y[i]] and x[i] == e:
            ans += 1
            vis[y[i]] = 1
            dfs(y[i])


nums, k = input().split()
k = int(k)
nums = list(nums)
length = len(nums)
x, y = [0], [0]
for _ in range(k):
    a, b = map(int, input().split())
    x.append(a)
    y.append(b)

t = [0] * (length + 1)
for i in range(length):
    ans = 0
    c = ord(nums[i]) - ord('0')
    nums[i] = c
    vis = [0] * 20
    vis[c] = 1
    dfs(c)
    t[i] = ans + 1
ans = 1
for x in t:
    if x != 0:
        ans *= x
print(ans)