B. la
题意：给定 \(n, m\) 和 \(1 \sim m\) 的排列 \(b\)。有一个长度为 \(n\) 的数组 \(a\)，所有 \(a_i\) 的值在 \([1, m]\) 中随机。定义一次变换为同时对所有 \(i \in [1, n]\) 执行 \(a_i \gets b_{a_i}\)。求期望多少次能将所有 \(a\) 变回原样。
首先将期望转化成答案总和除以 \(m^n\)。
考虑连边 \(i \to b_i\)，表示若 \(x = i\) 则 \(x\) 可以通过一次变换成为 \(b_i\)。
因为 \(b\) 是个排列，且 \(i\) 互不相同，所以图中所有点的入度和出度都为 \(1\)。也就是说整张图是由若干个环构成的。当然也包括自环。
令某个环的大小为 \(s\)。那么这个环上的任意一个点都可以通过 \(s \times k\)（\(k \in \mathbb N\)）次变换回到开始。
所以若我们令 \(i\) 所在的环的大小为 \(w_i\)，那么当 \(a\) 确定时答案为 \(\operatorname{lcm}(w_{a_1}, w_{a_2}, \dots, w_{a_n})\)。
暴力枚举 \(a\) 显然不行。考虑优化。
思考 \(\operatorname{lcm}\) 的性质。这个运算关注的是一个数字是否出现过，而跟这个数字出现的次数没有关系。例如 \(\operatorname{lcm}(3, 5, 7) = \operatorname{lcm}(3, 5, 7, 7, 7) \ne \operatorname{lcm}(3, 5)\)。
注意到 \(m \le 100\)。这意味着图中环的长度只有不超过 \(13\) 种。因为 \(1 + 2 + \dots + 13+14 = 105 > m\)。注意这里说的是长度的种类数而不是环的个数。
所以我们要计算的答案 \(\operatorname{lcm}(w_{a_1}, w_{a_2}, \dots, w_{a_n})\) 里，集合 \(\{w_{a_1}, w_{a_2}, \dots, w_{a_n}\}\) 的大小不超过 \(13\)。所以我们可以以 \(2^{13}\) 的复杂度枚举这个集合！算出 \(\operatorname{lcm}\) 后再算一个方案数乘起来就是答案！
具体的，我们枚举环长集合（即每种环的长度构成的集合）的子集 \(S\)。若我们能计算出有多少个 \(a\)，使得每个 \(a_i\) 都满足 \(w_{a_i} \in S\)，且对于每个 \(v \in S\) 都存在至少一个 \(a_i = v\)。那么这样的 \(a\) 的数量与 \(\operatorname{lcm}_{v \in S} v\) 的乘积再累加即可计算最终答案。
有点抽象。我们再明确一下当前的任务：
- 计算有多少个 \(a\)，满足：
- 对于每个 \(a_i\) 都满足 \(w_{a_i} \in S\)；
- 且对于每个 \(v \in S\) 都存在至少一个 \(a_i = v\)。（这个条件如果不满足就无法保证 \(\operatorname{lcm}a = \operatorname{lcm}S\)。）
我们预处理一个 \(c_i\) 表示多少 \(j\) 满足 \(i=w_j\)，即每种长度的所有环内的点的数量。
没有第二个条件很好做。答案是 \((\sum_{v \in S}c_v)^n\)。这是因为 \(a\) 的每一位都有 \(\sum_{v \in S}c_v\) 种方案。令 \(g(S) = (\sum_{v \in S}c_v)^n\)。
我们令有了第二个条件后的答案为 \(f(S)\)。那么可以容斥。即：
\[f(S) = \sum_{T \subseteq S} (-1)^{|S| - |T|}g(S) \]所以答案为：
\[\sum_{S \subseteq U} f(S) \times \operatorname{lcm}_{v \in S}v \] 标签：dots,13,sum,9.12,答案,lcm,operatorname,模拟 From： https://www.cnblogs.com/2huk/p/18410030