CF1746F Kazaee

· 2024-10-20 · # 模拟 # Atcoder # Codeforces # 数据结构 # 题解

容易发现如果满足题目要求那么一定满足 $k\mid \sum\limits_{i=l}^r a_i$ ，但是并不是必要条件，所以可以把 $a_i$ 随机映射到一些 $b_i$ 上然后多跑几次就行了，感觉挺典的。

考虑分析一次操作的的正确概率：

假设 $x$ 被映射为了 $y$ 满足 $k\mid cnt_x\times y$ 而且 $cnt_x\nmid k$ ，那么就近似于需要满足 $y\mid k$ ，可以理解为其概率为 $\dfrac{1}{k}$ ，所以在 $k$ 为 $2$ 的时候随机 $40$ 次左右就可以求解出答案了。