题解：AT_arc187_e [ARC187E] Replace Triplets

_determination_ · 2026-11-10 16:44:19 · 题解

all in 这题差一点场切，破防了。

首先环上的一个连续段是没有办法变化他的数字或者是删除某个连续段的，这也意味着如果有两个连续段值相同就爆了。

然后你考虑你能够进行的操作。其实也就是：

• 向左右割让一些点。
• 在左右释放一些大小为 1（大小更大没用）的连通块用来填充初始在序列中未出现的数字（如果新连通块原来出现了并且没连起来就肯定不合法了）。

那么我们先特判一下一次操作也没办法的情况，如果一次操作也无法进行，那么本来就是排列的时候答案就是 1，否则是 0。

然后我们可以选中一个可以操作的块。每次向右尽可能的割让，然后你就能发现每个连通块长度形成的序列大概形如 1+S,1,1\dots 1。一共 k 个连通块，S+k=n。

接下来我们就要把这 S 个点释放成连通块。我们考虑能够在哪里释放。最开始的时候我以为想在哪里释放就可以在哪里释放，但是这是错的。

我们考虑他为什么错了。因为如果我只扔过去一个东西那么是不足以支持他继续扔的。所以最后两次释放需要挂在一个连通块上。

也就是说我们需要有至少两个点释放在同一个间隔或者在一个连通块两侧，这样就是合法的释放方案的充要条件。考虑怎么计数这个东西。

考虑容斥。首先随便扔的方案数是 \binom{S+k-1}{k-1}。然后要去掉的方案就是“k 个区分的盒子，S 个不区分的小球，每个盒子最多放一个小球并且不能有两个相邻的盒子都放小球”的方案数。对于这个问题，我们的答案就是 \frac{k}{k-S}\binom{k-S}{S}。

这个式子是怎么来的？首先我们这是一个环所以我们钦定一个没放小球的点断环为链，系数是 k。然后我们发现每个放了小球的盒子后面都可以找到一个没放小球的盒子。也就是说我要在 k-S 个没放小球的盒子中找到 S 个盒子在前面挂一个装盒子的小球，系数 \binom{k-S}{S}。（我们断环为链的时候实际上不一定是在枚举的 i 处切了一刀，实际上枚举的是切割后第一个没装小球的盒子，也就是说如果有一个装了小球的盒子挂在了 i 前面那么切割处就是 i-1。）同时每个方案会被算 k-S 次，给一个 \frac{1}{k-S} 的系数。

由于我们这里只考虑了每个间隔放多少东西，因此我们要再乘上 S!。

现在我们考虑完了最后的连通块情况，但是我们计数的是最终排列数量，因此排列可能会旋转。

• 我们发现一直向右割让 2 可以让环旋转 2 格，而 n 为奇数的时候就可以等价旋转任意格。因此 n 为奇数的时候系数是 n。
• 同理，向右割让 3 可以旋转 3 格，因此当 S\ge 3 的时候系数也是 n。
• 如果只有两个连通块，设为 x,y。那么 x 向左向右各割让 1，然后 y 向左割让 2 就是转一圈。因此系数 k=2 时也是 n。
• 剩下的情况系数就是 \frac{n}{2} 了。

至此已经做完本题。提交的代码后面注释可以看一下笔者思维链。

Link.