不相交子排列 题解

思路

对一个已经确定的数组，总能贪心选择右端点最靠左的合法长度 $k$ 子数组。选中后从其后重新开始；交换论证说明，这不会减少最终能选出的子数组数量。

在当前尚未选中区间中，只需记录最长的元素互不相同后缀长度 $j$。在命中一个排列并立刻重置后，始终有 $0\le j<k$。

设处理完当前位置后，处于状态 $j$ 的数组数量为 $c_j$，这些数组的代价总和为 $s_j$。追加一个数时：

• 若它已在这段互异后缀中，按该数在后缀中的位置，新状态会分别成为 $1,2,\ldots,j$，每个新状态恰有一种选择；
• 若它不在后缀中，共有 $k-j$ 种选择，新状态为 $j+1$；
• 当 $j+1=k$ 时得到一个合法排列，所有这些序列的代价加一，并重置到状态 $0$。

做法

子任务 1 可以枚举全部 $k^n$ 个数组，对每个数组执行上述贪心，复杂度 $O(k^n n)$。

子任务 2 可以直接枚举旧状态与新状态，转移复杂度 $O(nk^2)$。

满分做法用后缀和优化。记

$$C_h=\sum_{j=h}^{k-1}c_j,\qquad S_h=\sum_{j=h}^{k-1}s_j.$$

则每轮转移为

$$c'_0=c_{k-1},\qquad s'_0=s_{k-1}+c_{k-1},$$

以及对 $1\le h<k$：

$$c'_h=C_h+(k-h+1)c_{h-1},$$ $$s'_h=S_h+(k-h+1)s_{h-1}.$$

第一项来自旧后缀中已有字符的选择，第二项来自追加未出现字符。处理 $n$ 个位置后，答案为 $\sum_{j=0}^{k-1}s_j$。

独立答案程序采用首次命中分解。先计算一段序列第一次出现合法长度 $k$ 窗口的结尾位置分布 $f_t$，再令 $A_m$ 为长度 $m$ 的所有序列代价和，则

$$A_m=\sum_{t=k}^{m}f_t\left(k^{m-t}+A_{m-t}\right).$$

该递推与标准程序的状态聚合路径独立，用于生成与复核答案。

复杂度

• 子任务 1：时间 $O(k^n n)$，空间 $O(n)$；
• 子任务 2：时间 $O(nk^2)$，空间 $O(k)$；
• 满分算法：时间 $O(nk)$，空间 $O(k)$。