题解

思路

按最后一个被选位置划分方案。每个非空优美路径的最后一组都有唯一的最早位置和最晚位置，因此不会重复计数。

做法

令 $best_i$ 为只使用前 $i$ 个位置能得到的最大组数，$ways_i$ 为对应方案数。可以跳过位置 $i$，继承前缀状态。

若最后一组的首尾位置为 $l,i$，必须满足 $c_l=c_i$。在开区间 $(l,i)$ 中还要选择 $k-2$ 个同色位置，共有

种。把它乘以 $ways_{l-1}$，即可转移到 $best_{l-1}+1$ 组。只保留最大组数并累加同最优值方案。$k=1$ 时每个位置单独成组，答案显然为一。

小规模可枚举所有子序列直接检查。

复杂度

预处理阶乘和逆阶乘后可在 $O(1)$ 时间求组合数。每组时间复杂度 $O(n^2)$，空间复杂度 $O(n)$。