模序列 题解

思路

令 $r=x\bmod y$，$q=\lfloor x/y\rfloor$。所有合法元素与 $x$ 模 $y$ 同余，因此可以写成 $a_i=r+k_i y$。其中 $k_1=q$，以后每一步把 $k$ 加一或清零。

于是必须有 $S-nr\ge0$ 且能被 $y$ 整除。记

问题变成构造长度为 $n$、总和为 $K$ 的 $k$ 序列。序列由一个 $q,q+1,\ldots,q+p-1$ 的前缀，以及若干个 $0,1,\ldots,L-1$ 的块组成。

做法

子任务 1 可以枚举后 $n-1$ 步选择“加一”还是“清零”，复杂度为 $O(2^n)$。

子任务 2 可以做位置动态规划。状态记录已经放置的元素数、当前 $k_i$ 与当前总和；从每个状态转移到 $k_i+1$ 或 $0$。状态数为 $O(nK^2)$，在该子任务限制内可通过。

满分算法先计算 dp[v]：用若干个从零开始的块凑出和 $v$ 所需的最少元素数。长度为 $L$ 的块贡献

且使用 $L$ 个元素。因此

同时记录最后一个块的长度以便恢复方案。枚举第一个特殊前缀的长度 $p$，其贡献为

若剩余值非负且 dp[剩余值] <= n-p，就恢复这些普通块，并用长度为一、贡献为零的块补足剩余位置。最后把每个 $k_i$ 还原成 $r+k_i y$。

正确性证明

任意合法操作都保持元素模 $y$ 的余数为 $r$，所以归一化后的转移恰为“加一”或“清零”。第一次清零前必形成从 $q$ 开始的连续递增前缀；以后每两次清零之间必形成从零开始的连续递增块。反之，任意这种分块都逐项满足合法转移。

动态规划枚举了每个普通块的所有可能长度，并取实现给定和所需的最短总长度，所以 dp[v] 不超过可用位置数当且仅当普通块可以放入；多余位置可由单元素零块补齐。算法又枚举了特殊前缀的全部可能长度，故若存在合法序列必会找到，所恢复序列也必合法且总和为 $S$。

复杂度

单个测试用例记归一化目标为 $K$。动态规划复杂度为 $O(K\sqrt K)$，枚举与输出复杂度为 $O(n)$，空间复杂度为 $O(K)$。由输入的总和限制，总复杂度可通过。