ARC100D Colorful Sequences

题意： 给定一个长为 的序列 ，保证每个数都 。

如果一个全部元素均 的序列中存在一个长度为 连续区间，恰好是 的排列，那么称这个序列为 「 −好序列 」。

给定长度 。求所有长度为 的 「 −好序列 」 共包含了多少个 （允许重叠）。

，，时限 。

---

发现对好序列计数较为困难（条件是或起来的），考虑取反，先统计在所有序列中 的出现次数，再减去不好序列中 的出现次数。

前者容易得到：枚举 的起点，确定了接下来的 个，其余位置随意。为 。

下面是后者的计算。

• Case 1： 本身是好序列。

包含 的序列必然是好序列，答案为 。

• Case 2： 中没有重复的数。

由于没有重复的数，各个颜色之间并没有本质区别。 为所有 “ 个不同 内数组成的序列” 的答案都是相同的。

于是，统计它们的和，并将答案除以 。

（定义一个区间是好的当且仅当其中没有重复的数）

记 表示填写了 个数，且极长好后缀的长度为 的方案数。

有转移 ：

第一条：放一个和倒数第 个重复的数。

第二条：放一个前 个没有出现过的数。这个数有 种可能。

记 表示填写了 个数，且极长好后缀的长度为 ，含有的长度为 的好区间总数。

转移和 相同，在 时额外加上 。

答案即为 。

• Case 3： 中有重复的数。

记 极长好前后缀的长度分别为 。

枚举 放置的位置的左端点 ，从 分别向左向右考虑。

对于左侧，令 ，然后 ， 即为左侧的方案数。

对于右侧，令 ，然后 ， 即为右侧的方案数。

上述 容易用前缀和优化做到 。