题解：CF2225G 大狗汪汪叫

· · 题解

以下讨论中默认 K 有序。

我们先考虑一个很简单的事情，如果 |K|=1 时会发生什么。方便我们认识问题的结构。

那们很简单，当且仅当 K_1=1 时有解。但是其他情况呢，考虑对于原序列 [0,n-1] 按照 K_1 找到 K_1 个剩余系，并且因为 3K_1 \leq n，所以对于一个剩余系一定至少有 3 个数了。那们我们一定能遍历剩余系的每一个数。并且我们发现，对于一个剩余系中的数可以乱放。然后增量考虑，我们可以用剩下的 K 联通这 K_1 个剩余系。

因为我们只需要关心联通，考虑建图。

我们有一个很简单的想法是对于 \forall i,j \ i \to (i+K_j)。然后我们要找到一条哈密顿路。挑战图灵奖，看上去就不太行吧。当然你可以乱搞冲过去。我们想一下我们前面的思考。依旧是增量考虑。我们既然前面都说到剩余系了，那我们就对剩余系建图吧。

我们还是发现我们的问题仍然不弱于找到一条哈密顿路。所以我们要在图的结构上下手段。我们已经解决了剩余系内部的问题了。我们继续去考虑原来的建图，类比一下，那们就是 \forall i, j \not ={1} \ i \to (i+ K_j) \bmod K_1。我们这个时候发现如果有贡献那们当且仅当 \gcd(pregcd,K_i)<pregcd。并且最后 \gcd(K)=1。相当于每次合并，生成一张按 \gcd(pregcd,K_i) 构造剩余系的图。然后我们图的结构相当于是对 \gcd 分层。我们在上面搜的时候相当于对于每一层考虑是在这一层还是往下继续搜，所以是对的。

然后构造排列的时候，我们从一个数里面进来，最后找到最小值。这样我们每次能够保证跨过剩余系的值最大是 2K_1。并且对于上一个最小值 x，变成 x+K_j 时，一定有 x+K_j > K_j \bmod {K_{1}}。所以我们这样构造是对的。

submission