作业

先考虑循环节，等概率选取一个长度为 $n$ 循环节为 $d$ 的字符串，考察最小表示在 $f$ 处的概率，若 $f \le d$，则概率为 $d^{-1}$，否则为 $0$。

先计算循环节为 $d$ 的字符串个数 $cnt(d)$，这个可以用莫反求，$cnt(d)=\sum_{c|d} \mu(c)26^{d/c}$。

然后问题就变成了，每次询问两个数 $m,n$，求等概率选择一个长度为 $n$ 的字符串和一个长度为 $m$ 的字符串，最小表示位置相同的概率。枚举位置 $f$，概率是 $(\sum_{d|n, f \le d}cnt(d)d^{-1}26^{-n}) \cdot (\sum_{d|m, f \le d}cnt(d)d^{-1}26^{-m})$。

观察到两部分都可以被分为至多 $\sqrt{A}$ 段相等的连续段，$A$ 是值域，复杂度 $O(n \sqrt{A})$。

交换

部分分在暗示做法。

最关键的一个性质：考虑第 $i$ 个数 $h_i$ 在最后被换到了 $p_i$ 的位置，那么最终状态下，第 $p_i$ 个数是 $(-1)^{i-p_i}h_i$，且操作次数是 $p_i$ 的逆序对数。

先考虑 $|h_i| \neq |h_j|$ 的部分分，按绝对值从大往小枚举，当前枚举到的数，要么丢到末尾且符号为正，要么丢到开头且符号为负。令 $dp(i,0/1)$ 表示，已经枚举了前 $i$ 个数，开头的数模 $2$ 是什么。转移只需要用 BIT 优化一下计算逆序对。

再考虑 $|h_i| \le 1$，由于符号翻转很烦，需要一点点的转化去掉它。令初始状态为 $a_1,\cdots,a_n$，目标状态为 $b_1,\cdots,b_n$，对于所有奇数（偶数也行）的 $i$，将 $a_i,b_i$ 取相反数，操作就变成了“交换相邻数，没有符号翻转”（理由：转化前后对于符号的要求均为，若 $|i-p_i|$ 为偶数，需要 $a_i,b_{p_i}$ 符号相同；若 $|i-p_i|$ 为奇数，需要 $a_i,b_{p_i}$ 符号相反）。

在转化后的问题上，需要对于一个 $-1,0,1$ 的序列求出，变成某个序列（中间一段为 $0$，左右两段 $+1,-1$ 交替排列）所需要的最小交换次数。

先做单组询问：给最终状态用 $[1,n]$ 顺次标号，给初始状态中的标号满足：对于所有 $x,y$，第 $x$ 个数 $y$ 在两个状态中的标号相同。操作次数就是初始状态标号的逆序对。

对于多组询问需要一点分讨，一个稍微简单的做法是，分 $0$ 左边的数有奇数还是偶数两种情况。对于同种情况，将 $0$ 的区间往右移动两步后，标号序列的变化也仅仅是将两个数的标号移到中间一段 $0$ 的前面，很容易用 BIT 计算逆序对的变化量。

考虑满分做法：$dp$ 状态一样，按绝对值 $x$ 从大到小枚举的时候，将 $+x$ 看成 $+1$，$-x$ 看成 $-1$，绝对值小于 $x$ 的看成 $0$。有时候 $0$ 会很多，但是计算逆序对的时候只需要分别计算：$(-1,0),(1,0),(-1,1)$ 之间的贡献，额外用 BIT 维护 $0$ 的位置即可。

复杂度 $O(n \log n)$。

复原

不会，咕