当前位置：首页 > news >正文

CF2039E Shohag Loves Inversions

news 2026/6/12 21:59:48

给你一个数列，初始数列为 $ a = [0, 1] $ ，现在重复进行以下操作若干次：

其中 $n\le 1e6$

题意的逆序对数显然不好维护，首先模拟一下操作过程：

初始的逆序对数 $k=0$ ，在一步步插入的过程中，若插入到了 $1$ 的后面，我们的逆序对数发生了第一次的改变，$k=0 \to k=1$ ，序列状态此时为 $0\dots010$。

然后一步步插入 $1$ ，当第一次插入到了最后一个 $0$ 的前面，我们逆序对数再次发生改变 $k=1\to k\ge 2$

再次插入 $2$ ，当我们一直插入到序列末尾的 $2$ 连续段之中时，逆序对数不变，如果插入到了除此之外的前面的任意一个位置，$k$ 的值发生改变。

我们发现当 $k\ge 2$ 时无论如何操作，最终的过程都与 $k=2$ 同理，所以此时我们发现问题可以分析成三种子问题：$k=0$，$k=1$，$k\ge 2$ ，我们最终只需要把这三种问题形成的序列种数相乘即可。

$k=0$ ，序列一定为 $0\dots 01$
$k=1$ ，序列一定为 $0\dots 0101\dots 1$
$k\ge 2$ ，可以设计 $dp$ 状态，观察到若存在两个不同的刚刚升级完的序列，那么此时无论如何插入新逆序对数的位置，对于方案数都不会有影响，所以此时的序列方案数仅与序列长度相关，所以可设 $f_i$ 表示序列长度为 $i$ 的刚刚升级完的序列方案数为 $f_i$ ，那么我们此时就分为两种情况进行插入：
1. 插入序列末尾的 $k$ 连续段，对于逆序对数无影响
2. 插入 $k$ 连续段前一个位置之前，逆序对数改变
那么我们就有转移 $f_i=\sum_j j\times f_j$ 。