题意： 初始时 $a = [0,1]$，每次更新将 $a$ 逆序对的数量 $k$ 插入其中，求最终长度为 $n$ 的序列的数量。
以下均设当前的序列逆序对的数量为 $k$。
首先需要通过观察得出一个性质，当序列第一次出现 $k > 1$ 的时候，若将 $k$ 插在中间的位置，会使得 $k’ > k$，在末尾插入则 $k’ = k$。设 $f_i$ 表示长度为 $i$ 且当前第一次出现 $k > 1$ 时，变为长度为 $n$ 的序列的数量。剩下还有 $n - i$ 次操作，可以将 $k$ 均插入末尾，或者在末尾插入若干个以后再将 $k$ 插入中间的 $i$ 个位置之一，因此可以得到以下转移：
现在我们讨论整一个序列均为 $k \le 1$ 的情况。显然 $k = 0$ 时就只有 $\underbrace{00 \cdots 0}_{n - 1}1$ 这一种。而 $k = 1$ 时应为 $\underbrace{00 \cdots 0}_{x}010\underbrace{11\cdots1}_{n - x - 3}$，其中 $x \in [0,n - 3]$，故有 $n - 2$ 种。所以说，$k \le 1$ 时，共有 $n - 1$ 种。
最后考虑 $k \le 1$ 转移至 $k > 1$ 的情况，显然只有 $k = 1$ 时才有可能。因此对于 $\underbrace{00 \cdots 0}_{x}010\underbrace{11\cdots1}_{n - x - 3}$ 类型的串，我们需要找到第一个 $1$ 所出现的位置。不难发现第一次出现 $k > 1$ 的序列时至少由长度为 $3$ 的 $010$ 转移而来，共会产生 $2$ 个长度为 $4$ 且 $k > 1$ 的串 $1010,0110$。一般化的，若在长度为 $i$ 时第一次出现 $k > 1$，则这个长度为 $i$ 的串共会有 $\sum \limits_{j = 2}^{i - 1} = \frac{i(i - 3)}{2}$ 种情况。举个例子，若 $i = 5$，则可能由 $0010,0101$ 转移出 $5$ 种情况。
综上所述，最后的答案就是 $n - 1 + \sum \limits _{i = 4}^n \frac{i(i - 3)}{2} f_i$。直接后缀和进行处理即可，时间复杂度 $O(n)$。
参考代码：
1 |
|
