题解

思路推导

序列长度为 $n+1$，值域中只有 $n$ 个数，并且每个数至少出现一次，因此恰有一个数出现两次，其余数各出现一次。若忽略这两个相同元素，选择 $k$ 个位置共有 $\binom{n+1}{k}$ 种；只需扣除会得到相同子序列的重复选择。

做法

设重复值的两个位置为 $l<r$，位置从 $0$ 开始编号。位于区间 $[l,r]$ 外的元素数量为

两组不同的位置选择会得到同一子序列，当且仅当它们分别选择重复值的两个出现位置，而其余 $k-1$ 个位置全部从区间外选取。因此长度为 $k$ 的重复计数为 $\binom{s}{k-1}$，答案为

预处理 $0$ 到 $n+1$ 的阶乘与逆阶乘，即可在常数时间求每个组合数并依次输出答案。

正确性证明

每个 $k$ 元位置集合都唯一确定一个长度为 $k$ 的子序列。由于只有一个值重复，两个不同位置集合产生相同内容时，它们的差异只能是选择了该重复值的不同出现位置。

若还选择了两个重复位置之间的某个元素，替换重复值出现位置会改变这个元素与重复值的相对顺序，所得子序列不同。因此，重复的两种选择中，其余 $k-1$ 个位置必须全部在 $l$ 左侧或 $r$ 右侧；反之，从这 $s$ 个外部位置任取 $k-1$ 个，分别搭配两个重复位置，确实得到同一子序列。这样的重复恰有 $\binom{s}{k-1}$ 个。

所以从全部 $\binom{n+1}{k}$ 个位置选择中减去它们，恰好得到不同子序列数量。对每个 $k$ 分别计算，算法正确。

复杂度分析

阶乘与逆阶乘预处理、寻找重复位置以及输出答案均为 $O(n)$；空间复杂度为 $O(n)$。