题解 P9267 [PA 2022] Walizki

· · 题解

对于每个有传送带的平台 i，系统复位的条件是，到达该平台的行李箱数恰好是 r_i​ 的倍数。

直接计算到达每个平台的行李箱数是困难的，但是根据上面的结论，到达每个平台的行李箱数都是其传送带数量的倍数，因此其连接的每条传送带传出的行李箱数也一定相等。

将最开始放在 1 号平台上的一个单位流量视作整体处理过程的基准。接下来，每个平台 i 接收到的流量（记作 flow_i）则可以表示：如果我们放出一个单位流量的行李箱，那么平台 i 最终收到的箱子为 flow_i 个单位流量，显然这是个有理数。

对于一个拥有 r_i 条传送带的平台，传送箱子时均分给每条传送带，所以每条传送带传出的流量为

f_i = \frac{flow_i}{r_i}.

传送带仅从较小编号的平台通向编号更大的平台，这保证了整个系统构成一个 DAG，使得我们可以按编号从小到大开始依次计算 flow_i。

对于每个有传送带的平台 i，总共处理了 X​ 个行李箱后，该平台收到的行李箱数为

X \times \mathit{flow}_i.

由于平台的传送带采用循环调度，只有当上面这个数是 r_i 的倍数时，平台的状态才会复位。换句话说，我们要求

X \times \frac{flow_i}{r_i} \in \mathbb{Z}.

也即

X \times f_i \in \mathbb{Z}.

不妨假设 f_i 的最简分数表示为 \frac{p_i}{q_i}，其中 p_i,q_i\in \mathbb{Z}^+ 且 \gcd(p_i,q_i)=1，那么上式等价于

q_i \mid X.

可知

X = \mathop{\text{lcm}}\limits_{i=1}^n\ q_i.

即为答案。

显然 X 的值可能很大，又因本题涉及到分数运算，因此使用 Python 实现。

from fractions import Fraction
from math import lcm

n = int(input())
to = []
for i in range(n):
    to.append([j - 1 for j in list(map(int, input().split()))[1:]])
flow = [Fraction(1)] + [Fraction(0)] * (n - 1)
X = 1
for i in range(n):
    if to[i]:
        f = flow[i] / len(to[i])
        X = lcm(f.denominator, X)
        for j in to[i]: flow[j] += f
print(X)