序列

有一个序列,初始为空。

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

求结束时序列中所有数的和的期望。对取模。

期望 DP

概率期望二元组

对于事件,设其发生的概率是,设其期望的贡献为。那么称为事件对应的概率期望二元组。

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

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

因此。其中表示基本事件对随机变量的值的贡献。

例如是一个事件,如果中等概率随机,那么

对于两个互斥事件中有一个发生等价于这个事件的发生,记作。那么对应的概率期望二元组可定义如下运算:

对于两个互斥事件,那么同时发生等价于中恰有一个基本事件中恰有一个基本事件同时发生,记作

是很好证明的,因此我们主要证明

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

可以证明乘法对加法有分配律。乘法的单位元是,加法的单位元是

题解

表示把长度为的空序列的第一个位置变成的概率(不考虑第一个位置的前一个位置上的数是啥)。

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

写的时候用概率期望二元组来实现会很方便。答案是对应的期望。

注意到我们合成的最大的数是。因此可以对取 min,因此朴素算法的时间复杂度是的。

使劲前缀和后缀和优化可以做到

代码

取石子

堆石子,第堆石子有个。A 和 B 轮流取,A 先手。规则如下:

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

求谁获胜。

博弈论 SG 函数

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

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

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

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

如果给出的初始局面里出现了的堆,那么先手必胜。

否则两人在执步过程中必然不会造出,因为这会导致对方必胜。

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

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

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

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

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

SG 值暴力计算

Food Court1

个序列,要求维护次操作:

  • :在第到第个序列的末位处分别插入个数字
  • :删除第到第个序列的开头的的数字。如果序列长度不足就把整个序列清空。
  • :询问第个序列的第个数字是啥。如果序列长度不足输出

线段树 树状数组

这是一道基本功题。

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

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

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

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

表示在时刻被插入的数字个数。设表示在时刻被插入的数字的值。

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

接下来考虑 Leave 操作。

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

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

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

总复杂度

Road Construction2

给出个点,求曼哈顿距离下前小的点对。输出他们的距离。

注:时限秒。

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

算法一

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

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

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

算法复杂度未知。

能过,而且跑得飞快。

代码

算法二

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

复杂度

给出一个长度为的 01 序列,问有多少长度为的排列,使得,有

DP 状圧

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

  1. 的两边的数不能是 2 倍关系。
  2. 的两边得是 2 倍关系。

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

  1. 枚举所有长度为的 01 序列,计算关于合法的排列数,容斥系数是
  2. 枚举所有长度为且当时有的 01 序列,计算关于合法的排列数,容斥系数是

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

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

表示考虑排列的前个数字,其中最后的个数字构成的倍数链,除去前个数字用掉的链,长度为的链还剩下个,的带上容斥系数的和。

因为,所以状态里只用记长度小于等于的链数。

转移时考虑的值:

  1. ,那么相当于延长最后一段链,转移到
  2. ,那么就要把最后一段链结尾,然后从剩下的链中截一段出来填进去。会转移到。这里的指截一段长度为的数链出去后新的状态。具体实现见代码的 trans 函数。

接下来考虑复杂度。

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

  • 长度为的链不超过个。
  • 长度为的链不超过个。
  • 长度为的链不超过个。
  • 长度为的链不超过个。
  • 长度为的链不超过个。
  • 长度为的链不超过个。

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

时间复杂度

代码

Literary Trick

给出两个字符串,判断他们的编辑距离是否大于。如果大于输出,否则输出他们的编辑距离。

时限

DP SA

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

  • 表示的最小编辑距离。这个 DP 的时间复杂度为
  • 表示的最小编辑距离。这个 DP 的时间复杂度为
  • 表示最大的,使得的编辑距离为

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

时间复杂度

(但其实 SA 跑得没有暴力 LCP 快)

代码

Lovely Painting

给出一个的正整数矩阵,定义一个四元组是个框当且仅当:

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

分治 数点

首先我们设分别表示从往左右上下能延伸的最长距离。

那么对于两个点,若,则以为左上角,为右下角的矩形构成一个框。

直接四位数点是的。

考虑分治。对于当前的的矩形,不妨设

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

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

那么跨过中线的框的个数就是

由于两者是对称的,以计算为例。

对于左边的一个点,若,那么这个点就有可能成为 “C” 型路线的一部分。这时可能会想到:枚举,其中,然后判断是否能延伸到中线,即判断是否成立。不过这个思路目前看不到很好的优化。

不妨换个角度。想办法强制成立。也就是说我们按照某种顺序来计算贡献和。

具体地,考虑 “C” 型路线的上下边界,假设分别是)。如果,那么不论从第行的哪一列出发,只要 “C” 型路线的竖线能从第行延伸到第行,就一定可以再沿着第行走到中线。

所以我们记表示:从出发,往左走到任意的某一列,然后往下走走到第行()的方案数。

同时记表示:从出发,往左走到任意的某一列,然后往走走到第行()的方案数。

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

那么有。换言之我们将点对分两类分别计算方案数。

考虑时间复杂度。每次分治我们都选择中较小的作为中线。设,那么中线长度就是的。根据主定理

代码

1. 来源:JOISC(Japanese Olympiad in Informatics Spring Camp Online Contest) 2021 Day1 T3。

2. 来源:JOISC(Japanese Olympiad in Informatics Spring Camp Online Contest) 2021 Day2 T2。

Sequence Counting

DP

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

以本题为例,设表示考虑已经填好了,并且前个数的最大值为,且钦定的最小值是的方案数。

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

DP 的转移则是枚举的值,然后转移到对应的位置。

答案是

朴素的 DP 时间复杂度,前缀和优化一下可以做到

注意到序列里不同的数最多有个,因此我们可以想办法算出表示序列中只出现了且每个值都出现过的方案数。那么答案就是是题面中的)。这个可以容斥计算(也可以理解为是二项式反演)。

这样时间复杂度就优化为了

代码