CF gym 105384 K. Knocker 题解

Danielcdo · 2025-11-10 07:42:12 · 题解

Link

题目概述

给定一个序列 A，每次操作可以选择一个正整数 x，将每个元素 A_i 变为 A_i \bmod x。问执行任意次操作后，能变成的不同序列个数。

题目转化

一眼结论题，还不简单。

由于每次操作都是对整体进行操作，因此初始就相等的元素一定全程都相等，所以我们不妨先对 A 去重。由于操作中大的数最容易受到影响，所以可以先对序列 A 从大到小排序，即 A_1>A_2>\dots>A_n，方便之后的讨论。

假设序列的最终形态为序列 B。如果我们直接从 A 下手，考虑它能变成哪些 B 会非常复杂，难处理算重的情况，也不好计数，因此我们反向考虑，B 满足什么条件是合法的？可以怎么构造出？

感觉还是无从下手啊，我们可以先把 A_i\le20 的特殊性质打出来，输出所有合法的 B 观察规律，一下是一些输入的其中一些输出：

输入 1：

10
1 2 3 4 5 6 7 8 9 10

输出 1：

1 2 3 4 5 6 0 1 2 3
1 2 3 4 0 1 2 3 4 0
1 2 3 0 1 2 3 0 1 2

输入 2：

8
1 3 5 7 9 11 13 15

输出 2：

1 3 5 7 9 1 3 5
1 3 5 7 0 0 2 4
1 3 5 0 2 1 3 5

从这几组例子中我们可以明显感受到，从序列 A 到序列 B，有很多组相邻位置的差是没有发生变化的。我们尝试研究每个元素变化减少的值：

根据刚才发现的规律，我们可以大胆的猜测：y_1=y_2=\dots =y_p ，由于这些 y_i 都相等，因此设 y 为它们共同的值。但猜测毕竟只是猜测，需要严格的理论证明。

首先我们假设只进行了一步操作，设模数为 x，则根据模运算的定义可知：

联立以上式子可得 y_1=y_i，由于每次操作都满足此性质，因此多次操作的最终结果也满足，得证。

也就是说，当我们知道 y 的值后，就能依次确定:对于任意的 A_i\ge y，B_i=A_i-y，由于这数都是减去相等的 y，因此大小关系不变。

接着我们发现，虽然最终值已经确定，但中间的多次操作仍然复杂，因此考虑将多次操作简化为一次操作，即：选择一个 y 满足 A_1-y<\frac{A_1}{2}（因为一个有效的模运算至少使得原数减半），然后让前 p 个位置同时减去一个 y，这样我们就确定了 B_{1 \dots p} 的值。

然后就是确定第 p+1 个位置到第 n 个位置的值，我们发现这个问题与我们的初始问题相似，是初始问题的一个子问题，所以考虑使用记搜或者 DP 来解决。这里处理子问题时需要满足一个限制：选择的模数必须大于 B_1 的值，不然在处理子问题时，又会影响到我们前面已经确定的 B_1 的值。

算法流程

DP 具体实现部分，看懂了上面的解决这道题就很简单了，这里还是简单描述一下实现。

首先，将序列 A 从小到大排序然后去重。定义 f_{i,j} 表示前 i 个位置已确定，且使用模数的最小值为 j 时的方案数。

接着，考虑对于位置 i 进行转移。简单枚举 B_i 的值 k，因此 y=A_i-k，然后我们从当前位置往前找到第一个 A_p<y，根据刚才的结论可知位置 p+1 到 i 都已确定，因此可以直接从位置 p 转移到当前 i。枚举前 p 个位置的选择模数的最小值为 u 从 k+1 到 500，转移：