CF1867D Cyclic Operations 题解

Planetary_system · 2025-08-12 22:13:29 · 题解

题面解释：

通过构造长度为 k 的序列 l (元素不重复) 将 l_{(i\bmod k)+1} 赋值给 a_{l_i}，达成目标序列。

思路分析：

首先式子中最关键的一步是取模后加一，不难发现此处可以转换成环。那么我们考虑建图，i 向 b_i 建立有向边。

考察样例 QWQ，通过手模样例总结规律发现：

• 否则任意环的长度应为 k。

接下来证明：

• 若 k\ne1，如果不在一个环上，即一条链。那么我们可以构造 l 序列使只有末尾一个元素不正确，下次覆盖即可，故而链不考虑。
• 那么只考虑环，如果一个环长度为 k 那么任意破环成链即可。反之，永远有一个末尾元素无法正确。所以环的长度必须正好是 k。

证毕。实现是简单的。