znstz的博客

博客

Public Round #11 验题人题解

2023-07-19 20:55:24 By znstz

作业

先考虑循环节,等概率选取一个长度为 $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)$。

复原

不会,咕

评论

FireskyDD
什么时候会传t3题解?
  • 2023-07-19 22:40:38
  • Reply
Zexal
不会,咕。蚌埠住了。
  • 2023-07-20 10:59:16
  • Reply
zhaohaikun
不会咕
  • 2023-07-20 22:03:57
  • Reply
Dualqwq
T2 题解是不是按绝对值从小往大枚举啊?
  • 2023-09-28 16:21:40
  • Reply
nalemy
T3 真的咕了?
  • 2024-01-02 07:52:17
  • Reply
Diu
T3 真的咕了?
  • 2024-02-09 15:35:52
  • Reply

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。