题解

思路

用长度为 $n$ 的二进制串表示最终数组：保留的数对应 $1$，删除的数对应 $0$。一次操作删除恰好 $2k$ 个数，所以零的数量必须是 $2k$ 的倍数。

若没有删除任何数，方案一定合法。否则，一个串可达当且仅当存在某个 $1$，其左侧和右侧都至少有 $k$ 个 $0$。这是最后一次操作中被保留的中间元素所满足的条件，反向也可逐步恢复操作。

做法

子任务 1

枚举全部 $2^n$ 个二进制串，对每个 $k$ 直接检查零的数量与上述条件。复杂度 $O(n^2 2^n)$。

子任务 2

固定删除数 $d=2k,4k,\ldots$，令保留数为 $x=n-d$。全部串有 $\binom nx$ 个。坏串中，从左数第 $k$ 个零到从右数第 $k$ 个零之间没有 $1$；压缩这段连续零后，得到恰有 $2k-1$ 个零和 $x$ 个一的串，因此坏串数为

$$\binom{x+2k-1}{2k-1}.$$

用 Pascal 递推预处理全部组合数，复杂度 $O(n^2)$。

满分算法

预处理阶乘与逆阶乘，使组合数可在 $O(1)$ 时间求出。对每个 $k$ 枚举 $d$ 的倍数，答案为

$$1+\sum_{\substack{d=2k\\d<n}}\left(\binom nd-\binom{n-d+2k-1}{2k-1}\right).$$

所有 $k$ 的枚举次数为调和级数，总复杂度 $O(n\log n)$。

正确性证明

每次操作删除 $2k$ 个元素，故零数为 $2k$ 的倍数。最后一次操作保留的中间元素左右各选出了并删除 $k$ 个元素，因此对应的 $1$ 两侧各至少有 $k$ 个零；反过来，选择这样的中心并把两侧各 $k$ 个零作为最后一次删除，其余零可递归配对删除，所以条件充分。

固定 $x$ 后，不满足条件的串在左右第 $k$ 个零之间全为零。把这段压成一个零，与具有 $2k-1$ 个零、$x$ 个一的串一一对应，数量即 $\binom{x+2k-1}{2k-1}$。从全部 $\binom nx$ 个串中减去坏串，再遍历所有合法删除数并加入零次操作方案，恰得到所有可达数组且无重复。

复杂度

满分算法预处理时间 $O(N)$，单个 $n$ 的求解时间 $O(n\log n)$，空间复杂度 $O(N)$，其中 $N$ 是全部测试用例中的最大 $n$。