2021 省选三轮跟训日志 2

序列

有一个序列，初始为空。

每次往序列末尾等概率随机地添加一个$[1,m]$中的整数。如果出现两个相邻相同的数，值为$x$且$x<t$，那么就会合并为$x+1$。如果序列长度为$n$且无法合并，那么操作结束。

求结束时序列中所有数的和的期望。对$10^9+7$取模。

$n, m \le 1000, m\le t\le 10^9$。

期望 DP

概率期望二元组

对于事件$A$，设其发生的概率是$P(A)$，设其期望的贡献为$E(A)$。那么称$(P(A), E(A))$为事件$A$对应的概率期望二元组。

相对严谨地说，事件$A$等价于若干个基本事件的集合$x_1, \cdots, x_n$。每个基本事件发生的概率不一定相同，但是每个基本事件都是不可再拆分的，也是互斥的。

事件$A$的发生等价于$A$中恰好有一个基本事件发生。

因此$P(A) = \sum_{x\in A} P(x)$，$E(A) = \sum_{x\in A}P(x)v(x)$。其中$v(x)$表示基本事件$x$对随机变量的值的贡献。

例如$x_0 = 4$是一个事件，如果$x_0$在$1,2,3,4$中等概率随机，那么$P(x_0=4) = \frac{1}{4}$，$v(x_0 = 4) = 4$。

对于两个互斥事件$A, B$，$A$和$B$中有一个发生等价于$A\cup B$这个事件的发生，记作$C=A+B$。那么对应的概率期望二元组可定义如下运算：

$$(p_a, e_a) + (p_b, e_b) = (p_a + p_b, e_a + e_b) = (p_c, e_c)$$

对于两个互斥事件$A, B$，那么$A$和$B$同时发生等价于$A$中恰有一个基本事件$x_i$和$B$中恰有一个基本事件$y_j$同时发生，记作$AB$。

$P(AB) = P(A)P(B)$是很好证明的，因此我们主要证明$E(AB) = P(A)E(B) + E(A)P(B)$。

$$\begin{aligned} E(AB) &= \sum_{x\in A}\sum_{y\in B}P(x)P(y)(v(x)+v(y))\\ &= \sum_{x\in A}P(x)v(x)\sum_{y\in B}P(y) + \sum_{x\in A}P(x)\sum_{y\in B}P(y)v(y)\\ &= E(A)P(B) + P(A)E(B) \end{aligned}$$

因此可以对概率期望二元组定义如下运算：

$$(p_a, e_a)\cdot (p_b, e_b) = (p_ap_b, p_ae_b+e_ap_b) = (p_c, e_c)$$

可以证明乘法对加法有分配律。乘法的单位元是$(1, 0)$，加法的单位元是$(0, 0)$。

题解

设$x(i, j)$表示把长度为$i$的空序列的第一个位置变成$j$的概率（不考虑第一个位置的前一个位置上的数是啥）。

$$x(i, j) = [j\le m]\frac{1}{m} + x(i, j-1)x(i-1, j-1)$$

设$f(i, j)$表示把长度为$i$的空序列填满，且第一个位置的前一个位置上是$j$。并且要求在填的过程中$j$不能被合并的概率。

$$f(i, j) = \sum_{k + [j\ne t] \le j}x(i, k) f(i-1, k) + \sum_{j<k\le t} f(i-1, k) \sum_{j < p \le min(m, k)} \frac{1}{m} \prod_{p\le q < k} x(i-1, q)$$

写的时候用概率期望二元组来实现会很方便。答案是$f(n, t)$对应的期望。

注意到我们合成的最大的数是$n+m$。因此$t$可以对$n+m$取 min，因此朴素算法的时间复杂度是$O(n(n+m)^2m^2)$的。

使劲前缀和后缀和优化可以做到$O(n(n+m))$。

代码

取石子

有$n$堆石子，第$i$堆石子有$x_i$个。A 和 B 轮流取，A 先手。规则如下：

• 每次可从一堆中取$[a,b]$数量的石子。
• 如果谁取完某一堆，立刻判此人胜。

求谁获胜。

博弈论 SG 函数

我们回忆一下 SG 需满足的条件：

• 双人回合制：轮流执步。
• 公平竞争：两人遵守的游戏规则一样。
• 有限：对于任意局面，都可以在有限步数内结束。
• 一般游戏条件：不能动的输。

对于这个游戏而言，第 4 个条件似乎不太满足。因为如果你取完了某一堆，不论对手是否能动，都会判你胜利。

那么我们能否避免取完某一堆的局面出现？

如果给出的初始局面里出现了$a\le x_i\le b$的堆，那么先手必胜。

否则两人在执步过程中必然不会造出$a\le x_i \le b$，因为这会导致对方必胜。

因此我们可以将游戏规则改成：

• 每次可从一堆中取$[a,b]$数量的石子，且取完后该堆石子的数量不能落入$[a,b]$中。

原问题的第二个规则就可以不要了。

我们发现新的游戏满足 SG 条件，同时与老游戏等价。

因此就可以计算 SG 值找规律了。

SG 值暴力计算

Food Court¹

有$n$个序列，要求维护$q$次操作：

• $\text{Join}(l, r, c, k)$：在第$l$到第$r$个序列的末位处分别插入$k$个数字$c$。
• $\text{Leave}(l, r, k)$：删除第$l$到第$r$个序列的开头的$k$的数字。如果序列长度不足$k$就把整个序列清空。
• $\text{Service}(a, b)$：询问第$a$个序列的第$b$个数字是啥。如果序列长度不足$b$输出$0$。

$n, q, c \le 2\times 10^5, k\le 10^9, b\le 10^{15}$。

线段树 树状数组

这是一道基本功题。

考虑只有 Join 和 Service 操作的情况。

如果要在线处理，那么难以避免信息的分裂。以线段树为例，就需要将操作标记到 log 个区间上，查询的时候得在 log 个集合上二分，复杂度至少有两个 log，常数不小。

考虑离线处理。这时我们就需要关注操作的执行时间。不过我们发现，序列里的数的位置与操作的执行时间是正相关的——操作执行地越晚，数字的位置相对越靠后。因此我们想要在序列上定位，可以在时间上二分。

具体地，我们从$1$到$n$依次考虑第$i$个序列与其相关的操作。从第$i-1$个序列变到第$i$个序列，需要在某些时刻上加入操作，在某些时刻上减少操作。

设$a_i$表示在时刻$i$被插入的数字个数。设$c_i$表示在时刻$i$被插入的数字的值。

容易发现询问就变成了在$a$上 lower_bound。修改则变成在$a_i$上单点修改。这可以用树状数组维护。

接下来考虑 Leave 操作。

我们考虑去掉 Leave 操作。也就是说我们想办法求出每个 Service 操作真正询问的位置（相当于加上离开的人数）。这时我们不需要考虑插入的数字具体是啥，只需要考虑插入数字的个数。换言之我们要求维护

• 区间加
• 区间取 max
• 求单点的值

这可以用线段树维护。注意，这不用吉老师线段树。

总复杂度$O(n\log_2n)$。

Road Construction²

给出$n$个点$(x_i, y_i)$，求曼哈顿距离下前$k$小的点对。输出他们的距离。

$n, k\le 2.5\times 10^5$。

注：时限$10$秒。

K-D Tree 切比雪夫距离 二维数点

算法一

暴力的做法是维护一个堆，枚举点$u$，再枚举$v$，然后计算$u$到$v$的距离，插入到堆中，并且始终保持堆的大小在$k$以内。

考虑用 K-D Tree 优化这个过程。如果堆的大小已经达到$k$，并且$u$到$v$的距离大于堆中的最大元素，那么$(u,v)$就是无用的。

2-D Tree 上一个结点代表某个矩形以及这个矩形中按某一维排序的中位点。考虑将枚举$v$的过程改成在 2-D Tree 上 DFS。如果我们发现当前 DFS 到的矩形的四个角与$u$的距离的最小值大于堆中的最大元素（且堆的大小为$k$）那么我们就可以直接回溯了。

算法复杂度未知。

能过，而且跑得飞快。

代码

算法二

转成切比雪夫距离。然后二分。问题可以转化为求方形内的点数，可以二维数点。

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

简

给出一个长度为$n-1$的 01 序列$a_1,\ldots, a_{n-1}$，问有多少长度为$n$的排列$p_1,\ldots, p_n$，使得$\forall 1\le i < n$，有$[a_i = 1] = [p_i = 2p_{i+1} \vee 2p_i = p_{i+1}]$。

$n\le 40$。

DP 状圧

考虑把$1,2,\ldots, n$划分为$2$的倍数的链。那么对于$a$中长度为$k$的 1 的连续段，我们得拿出一段长度为$k+1$的链放上去。计算方案数的过程中有两个条件需要考虑：

1. $a_i=0$的两边的数不能是 2 倍关系。
2. $a_i=1$的两边得是 2 倍关系。

老规矩。计数题的思路有两个：不重不漏，或者容斥。本题很难不重不漏地计数，因此考虑容斥。有两种容斥方法都是可行的：

1. 枚举所有长度为$n-1$的 01 序列$b_1, \ldots, b_{n-1}$，计算关于$b$合法的排列数，容斥系数是$(-1)^{\sum_{i = 1}^n [a_i \ne b_i]}$。
2. 枚举所有长度为$n-1$且当$a_i = 1$时有$b_i = 1$的 01 序列$b_1, \ldots, b_{n-1}$，计算关于$b$合法的排列数，容斥系数是$(-1)^{\sum_{i = 1}^n [a_i \ne b_i]}$。

第一种相当于是把两个条件同时容斥了。第二种相当于把第一个条件容斥了。

以第二种容斥为例。考虑使用 DP 实现。

记$f(i, j, c_1, c_2, c_3, c_4, c_5, c_6)$表示考虑排列的前$i$个数字，其中最后的$j$个数字构成$2$的倍数链，除去前$i-j$个数字用掉的链，长度为$x$的链还剩下$c_x$个，的带上容斥系数的和。

因为$n\le 40$，所以状态里只用记长度小于等于$6$的链数。

转移时考虑$b_i$的值：

1. 若$b_i = 1$，那么相当于延长最后一段链，转移到$f(i+1, j+1, c_1, c_2, c_3, c_4, c_5, c_6)$。
2. 若$b_i=0$，那么就要把最后一段链结尾，然后从剩下的链中截一段出来填进去。会转移到$f(i+1, 1, d_1, d_2, d_3, d_4, d_5, d_6)$。这里的$d$指截一段长度为$j$的数链出去后新的状态。具体实现见代码的 trans 函数。

接下来考虑复杂度。

本题的状态数是很小的，可以再想办法压状态。比如用 BFS 写 DP。但简单计算一下可以发现，在 DP 过程中：

• 长度为$1$的链不超过$26$个。
• 长度为$2$的链不超过$11$个。
• 长度为$3$的链不超过$5$个。
• 长度为$4$的链不超过$3$个。
• 长度为$5$的链不超过$1$个。
• 长度为$6$的链不超过$1$个。

因此直接开个$8$维数组就行了。

时间复杂度$O(n\cdot 6\cdot 27\cdot 12\cdot 6\cdot 4\cdot 2\cdot 2)$。

代码

Literary Trick

给出两个字符串$S, T$，判断他们的编辑距离是否大于$k$。如果大于$k$输出$-1$，否则输出他们的编辑距离。

$|S|, |T| \le 5\times 10^5, k\le 5000$。

时限$7s$。

DP SA

有关编辑距离的 DP 方法有这么几种：

• 设$f(i, j)$表示$S[1, i]$与$T[1, j]$的最小编辑距离。这个 DP 的时间复杂度为$O(|S||T|)$。
• 设$f(i, j)$表示$S[1, i]$与$T[1, i-j]$的最小编辑距离。这个 DP 的时间复杂度为$O(|S|k)$。
• 设$f(i, j)$表示最大的$a$，使得$S[1, a]$与$T[1, a-j]$的编辑距离为$i$。

本题使用的则是第$3$种 DP。在转移的过程中需要使用 LCP 优化转移。

时间复杂度$O(n\log_2n + k^2)$。

（但其实 SA 跑得没有暴力 LCP 快）

代码

Lovely Painting

给出一个$n\times m$的正整数矩阵$M$，定义一个四元组$(a, b, x, y)$是个框当且仅当：

• $1\le a < x\le n, 1\le b < y\le m$。
• $\forall a\le i \le x, \; M_{ib} = M_{iy}$。
• $\forall b\le j\le y, \; M_{aj}=M_{xj}$。

也就是说四条边上的数相同的视作一个框。问$M$中框的个数。

分治 数点

首先我们设$L_{i,j}, R_{i,j}, U_{i,j},D_{i,j}$分别表示从$(i,j)$往左右上下能延伸的最长距离。

那么对于两个点$(a,b)$和$(x, y)$，若$x-L_{x, y}\le a < x\le a+R_{a,b}$且$y-U_{x, y} \le b < y \le b+D_{a, b}$，则以$(a, b)$为左上角，$(x, y)$为右下角的矩形构成一个框。

直接四位数点是$O(n\log^3n)$的。

考虑分治。对于当前的$r\times c$的矩形，不妨设$r \le c$。

那么我们将其分为左右两部分，计算跨过中线的框的个数。

对于左边我们记$c_1(i, j)$表示从中线上第$i$行（即$(i, mid)$）出发，到中线上第$j$行结束的 “C” 型路线的个数。同样的，对右边记$c_2(i, j)$表示从中线第$i$行出发到第$j$行结束的 “反C” 型路线的个数。

那么跨过中线的框的个数就是$c_1\cdot c_2 = \sum_i \sum_j c_1(i, j)\times c_2(i, j)$。

由于两者是对称的，以计算$c_1$为例。

对于左边的一个点$(a, b)$，若$b + R_{a, b} \ge mid$，那么这个点就有可能成为 “C” 型路线的一部分。这时可能会想到：枚举$i$，其中$a < i \le a+D_{a, b}$，然后判断$(i, b)$是否能延伸到中线，即判断$b + R_{i, b} \ge mid$是否成立。不过这个思路目前看不到很好的优化。

不妨换个角度。想办法强制$b + R_{i, b} \ge mid$成立。也就是说我们按照某种顺序来计算贡献和。

具体地，考虑 “C” 型路线的上下边界，假设分别是$i$和$j$（$i < j$）。如果$L_{i, mid} \le L_{j, mid}$，那么不论从第$i$行的哪一列出发，只要 “C” 型路线的竖线能从第$i$行延伸到第$j$行，就一定可以再沿着第$j$行走到中线。

所以我们记$d_1(i, j)$表示：从$(i, mid)$出发，往左走到任意的某一列，然后往下走走到第$j$行（$i < j$）的方案数。

同时记$d_2(i ,j)$表示：从$(i, mid)$出发，往左走到任意的某一列，然后往上走走到第$j$行（$i > j$）的方案数。

这两个都可以简单地前缀和处理出来。

那么有$c_1(i, j) = d_1(i, j) [L_{i, mid} \le L_{j, mid}] + d_2(j, i)[L_{i, mid} > L_{j, mid}]$。换言之我们将点对$(i, j)$分两类分别计算方案数。

考虑时间复杂度。每次分治我们都选择$r$和$c$中较小的作为中线。设$S = rc$，那么中线长度就是$O(\sqrt{S})$的。根据主定理

$$T(S) = T(S/2) + O(S + (\sqrt{S})^2) = O(S\log_2S)$$

代码

¹. 来源：JOISC（Japanese Olympiad in Informatics Spring Camp Online Contest） 2021 Day1 T3。 ↩

². 来源：JOISC（Japanese Olympiad in Informatics Spring Camp Online Contest） 2021 Day2 T2。 ↩

Sequence Counting

DP

本题的难点在于 DP 状态的设计。对于计数 DP 来说，DP 的状态一般会表示为「满足某种条件的方案数」。而这里的条件既可以限定要统计的对象本身的性质，也可以限定当前的方案空间的性质。

以本题为例，设$f(i, j, k)$表示考虑已经填好了$a_1, \ldots, a_i$，并且前$i$个数的最大值为$j$，且钦定$a_{i+1},\ldots, a_n$的最小值是$k$的方案数。

这个状态里的第三维限定的并非前$i$个数，而是后$n-i$个数。但实际上后$n-i$个数是未知的。因此它实际上限定的是方案空间，用通俗的话讲就是：它限定了这个状态能够转移到的状态集合。

DP 的转移则是枚举$a_{i+1}$的值，然后转移到对应的位置。

答案是$\sum_j \sum_k [j\ne k] f_{n-1, j, k}$。

朴素的 DP 时间复杂度$O(nk^3)$，前缀和优化一下可以做到$O(nk^2)$。

注意到序列里不同的数最多有$n$个，因此我们可以想办法算出$g_i$表示序列中只出现了$1, 2, \ldots,i$且每个值都出现过的方案数。那么答案就是$\sum_i \binom{K}{i} g_i$（$K$是题面中的$k$）。这个可以容斥计算（也可以理解为是二项式反演）。

这样时间复杂度就优化为了$O(n^3)$。

代码