板刷题单：https://www.luogu.com.cn/training/2018#problems

可以想到，每种情况都对应一个长度为 $n - 1$ 的排列。

考虑计算每条路径被经过了多少次， 先对原数组做差分。

记 $d(i)$ 为 $i \to i + 1$ 的长度，$f(i)$ 为 $i \to i + 1$ 的路径被经过的期望次数。

$E = \sum \limits _{i = 1}^{n-1}d(i) \times f(i)$

考虑如何计算 $f(i)$。

定义 $g(j,i)$ 为点 $j$ 向右融合经过 $i \to i + 1$ 这条路径的期望次数。

有：$f(i) = \sum \limits _{j = 1}^i g(j,i)$

问题在于计算 $g(j,i)$，考虑 $j$ 点能顺畅地右移到 $i + 1$，那么 $[j + 1,i]$ 间的点都已经右移。

表现在序列上，就是 $j$ 的出现位置一定在 $[j + 1,i]$ 之后。

可以考虑先在移动序列中对 $[j,i]$ 间的 $i - j + 1$ 个元素去序，然后将 $j$ 放在最后，剩余 $i - j$ 个元素进行全排列，放回原序列中。

$$ g(j,i) = \dfrac{(n-1)!}{(i - j + 1)!} \times (i-j)!$$

$$ g(j,i) = \dfrac{(n-1)!}{i-j+1}$$

这样就较为简单地推出了 $g(j,i)$，而不需要别的题解中我看不懂的奇怪式子。(

$$ f(i) = \sum \limits _{j=1}^i g(j,i) = (n-1)! \times \sum \limits _{j=1}^i \dfrac{1}{i-j+1}$$

还可以进一步化简：

$$ f(i) = (n-1)! \times \sum \limits _{j=1}^i \dfrac{1}{j}$$

而答案就是：

$$E = \sum d(i) \times f(i) = (n - 1)! \times \sum \limits _{i=1}^{n-1} (d(i) \times \sum \limits _{j=1}^i \dfrac{1}{j})$$

可以线性递推逆元，预处理调和级数前缀和做到 $O(n)$ 复杂度。

看上去就是动态规划之类的解法吧。题意转化为 $x \ge 0$，最小化 $f(x + N) + f(x)$，然后考虑。对于 $f(x + N)$，从后往前，每位对下一位的影响就是是否进位，而且进位也只进一位。

而 $x$ 的这位填多少？考虑填完之后，要么 $x + N$ 这一位为零，要么 $x$ 这一位为零。塞到状态里就可以了。

$g(i,0)$ 代表第 $i$ 位未进位， $g(i,1)$ 代表第 $i$ 位向 $i+1$ 进位了，然后转移随便搞搞就行了。

看上去就很神的题，感觉很老，但就是不会做。

首先，区间异或，可以发现异或满足差分性质，因此对 $[l,r]$ 区间异或可以拆成在差分数组上对 $l$ 与对 $r + 1$ 异或。

感觉很图论，令图上每个点都代表 $i$ 点，然后对 $l$ 点与 $r + 1$ 点连边，代表可以通过该边翻转颜色。

如果选择了该操作，就选择了该边。

一个点的最终值，与它相连的边的奇偶性有关。

对于每一个联通块，相连的两个黑点总是可以同时变白，而中间的点总是可以不改变状态。那么统计黑点数量，如果可以两两消去就存在解。

那么如何统计方案呢？可以用类似差分的方法标记路径，每次遇到一个黑点就打标记往上消，然后遇到另一个黑点的标记，消了两次就相当于没变化了。

答案还要按从小到大输出。

如果不考虑取模，那么对应的 $j$ 一定有 $a_j < a_{j + 1}$，而考虑取模后有可能不成立。可以发现，仅当进位后，有可能不成立，但也只是有可能。因为可能原本值很大，加上后取模也大，那么列个式子：$a_j < a_j + d_i - m$，就可以发现 $d_i > m$ 是不可能的。

那么当且仅当 $a_{j} + d_i \ge m$ 时，有 $a_j > a_{j + 1}$，而当且仅当 $d_i = 0$ 时，有 $a_j = a_{j+1}$.

只要能够统计这两种，就能减出我们需要的答案了。

$d_i = 0$ 很好统计，算算有多少个对应的 $j$ 即可。

而 $d_i > 0$，需要计算进位，可以直接用总和去除。