题解：CF1626F A Random Code Problem

Abczzzzz · 2026-04-25 15:23:58 · 题解

总贡献问题，把每一个数的贡献拆开计算。考虑 a_i 的贡献，本质上是在选到的时候计算贡献。设 f_{i,j,k} 为 i 进行 j 次操作之后值为 k 的概率。下一轮选中 i 的概率当然就是这个值乘以 \frac{1}{n}，分选到了和没选到转移即可。

考虑把每一个 a_i 的 DP 值加在一起，发现转移、取答案等都可以正常运行。

需要对 lcm 取模缩小范围。