作业
先考虑循环节,等概率选取一个长度为 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)。
复原
不会,咕