小火车

idea from 神秘人, data, solution from hehezhou

算法一

我会按照题意模拟！

直接枚举 $b_i=0,-1,1$，判断是否合法。

时间复杂度 $O(3^n)$，期望得分 $20$。

算法二

我会 meet in middle！

把所有数均匀分成两半，分别对两侧求出填上 $b$ 以后，能得到哪些和。

考虑找出将两侧合并出 $0$ 的方案，对左侧某个和为 $x$ 的组合查询右侧能否组合出 $-x$ 即可。

时间复杂度 $O(3^{n/2})$，期望得分 $40$。

算法三

我们还没用到 $2^n\gt p$ 呢！

题意等价于找出两个不相交的子集，使得集合元素和相等。这又等价于找出两个不相同的子集，使得集合元素和相等，后者到前者只需删去两个集合的公共元素即可。

那么这和 $2^n\gt p$ 有什么关系呢？实际上这个条件保证了本题一定有解，因为子集有 $2^n$ 个，而子集和只有 $p$ 种，由鸽巢原理可以得出一定有两个子集的和相同。

直接搜出所有子集和，找到两个相同的即可。

时间复杂度 $O(2^n)$，期望得分 $40$。

算法四

对于数据随机的部分，算法二和算法三简单改造以后都可以通过，背后的理论是生日碰撞。

对于算法二，在两侧随机 $O(\sqrt{p})$ 种方案，对于算法三，随机 $O(\sqrt{p})$ 个子集，有极大概率能找到解。

时间复杂度 $O(\sqrt{p}n)$，期望得分 $60$。

算法五

我们从鸽巢原理入手。

假想有 $p$ 个桶，分别编号为 $0$ 到 $p-1$，将子集放进子集和对应的桶。

那么 $p$ 个桶一共装了 $2^n$ 个子集，一定有一个桶至少装了两个子集，我们的目标就是找到这个桶，称包含超过一个子集的桶为目标桶。

更近一步，对于一个桶的区间 $[l,r]$，如果这些桶中装了超过 $r-l+1$ 个子集，那么 $[l,r]$ 中一定存在一个目标桶。

令桶区间 $[l,r]$ 中一共装了 $s_{l,r}$ 个子集。

如果 $s_{l,r}\gt r-l+1$，那么对于 $k\in[l,r)$，$s_{l,k}\gt k-l+1$ 和 $s_{k+1,r}\gt r-k$ 至少有一个成立，否则 $s_{l,r}=s_{l,k}+s_{k+1,r}\leq r-l+1$ 矛盾。

因此，我们只需要能快速计算 $s_{l,r}$，就可以通过二分，在 $\log p$ 次询问内定位到某个目标桶。

而计算 $s_{l,r}$，同样使用 meet in middle，把数分为两侧，计算出两侧的所有子集和并提前排序后，每次询问双指针即可。单次询问时间复杂度 $O(2^{n/2})$。

定位到某个目标桶后，同样使用 meet in middle 找到对应子集即可。

时间复杂度 $O(2^{n/2}\log p)$，期望得分 $100$。

题外话

其实这道题是一篇论文的子问题。但是原论文中的做法比算法五复杂许多。

这题数据实在太难造啦！

造题人想破头只想出来一个构造：

1. 给定 $n$，令 $p=2^n-1$。

2. 先令 $a_i=2^i$，再随机取 $l\in [0,n-1]$ 使 $a_l$ 特殊的变为 $2^l-1$。

3. 随机打乱，随机将一些数变为相反数。

4. 随机取 $x$ 满足 $x$ 与 $p$ 互质，将所有 $a_i$ 变为 $a_ix\bmod p$。

这个构造的答案只有两组，是理论最低值。那么聪明的大家能否找到其他的构造方式呢？

神隐

idea from skip2004, data from skip2004, solution from skip2004, skyline

这题其实给出每条边的编号也是简单的，但是略微增加代码难度，就去了。

算法一

我们直接进行 $n-1$ 次询问，每次询问加入一条边，此时有一个连通块有两个点，就是这条边的两端。

询问次数 $n-1$，时间复杂度 $O(n^2)$，可以通过子任务 $1$。

算法二

如果一个询问包含一条边，那么这条边两边的点就会在一个连通块中，不然就不在。

考虑进行如下 $2\lceil \log_2 n \rceil$ 次询问，第 $2i - 1$ 与 $2i$ 次分别加入二进制第 $i$ 位为 $0/1$ 的边。

考虑两个点，如果恰好出现在其中 $\lceil \log_2 n \rceil$ 个连通块中，就是树上一条边。

如果使用暴力的实现，时间复杂度为 $O(n^2\log_2 n)$，可以通过子任务 $1,2$。

如果使用精细的实现（类似于算法四），时间复杂度为 $O(n\log_2 n)/O(n\log_2^2 n)$，可以通过子任务 $1, 2, 4$。

算法三

from p_b_p_b

对于任意两条相邻的边：

必须有询问只有第一条边没有第二条边，且有询问只有第二条边没有第一条边。

不然容易构造多种情况询问结果相同。

算法二显然是满足的，但是询问次数过多，我们可以使用以下方法：

选取 $[0, 2^T)$ 中，二进制 $1$ 个数为 $\frac{T}{2}$ 的所有数作为编号进行二进制分组。

其余部分和算法二相同。

如果使用暴力的实现，询问次数为 $(1+o(1))\log_2 n$, 时间复杂度为 $O(n^2\log_2 n)$，可以通过子任务 $1,2,3$。

算法四

from skyline

注意到边是所有 $2k$ 次询问中恰好 $k$ 次在一个连通块中的点对（这里定义 $k$ 为询问次数的一半），以及任何点对最多一共出现在连通块中 $k$ 次，我们考虑以下搜索方法：

solve(当前限制下连通块交, 当前已经处理的询问轮数, 当前已经被要求强制在一个连通块里的轮数)

如果点集大小是 $1$，没有继续找其中点对的必要，可以立即返回。

如果当前已经被要求强制在一个连通块里的轮数达到 $k$，点集描述的就是一对边，加入答案并返回

如果不强制此轮在一个连通块里仍然可能最后 $k$ 轮在一个连通块，我们尝试不强制的情况进入下一层搜索（连通块交不变）

如果强制此轮在一个连通块里，我们使用时间戳+类似基数排序的手段来关于连通块交大小线性地对连通块做出划分并进入下一层搜索

我们下面将证明上面的策略是 $O(n2^k)$ 的。我们暂不考虑立刻返回的情形。由于点集大小大于 $1$，树上连通块中点数比边数多 $1$，从而点数不超过边数两倍。我们只需要证明总边数是 $O(n2^k)$ 的。假设当前已经处理的询问轮数是 $x$, 当前强制要求在一个连通块里的轮数是 $y$，如果不强制会传导所有的边，而强制会去掉一半的边（此轮询问中没有询问的边被割了没法进入下一层搜索，更严格的说明方法是所有 $C_{2k}^k$ 种询问策略在 $y$ 轮强制中都在待处理边集中的不超过 $C_{2k-y}^{k-y} \leq \frac{C_{2k}^k}{2^y}$ 种，从中随机挑选 $n-1$ 个询问策略分给边期望有不超过 $\frac{n-1}{2^y}$ 条被保留，当然你也可以精心挑选符合条件的策略给边），所以进入 solve(any, x, y) 的边数是 $O(\frac{nC_x^y }{2^y})$ 的，而我们有限制 $(y \leq x \leq y+k, y < k)$, 满足此条件的 $\frac{C_x^y }{2^y}$ 之和是 $2^{k+1}-2$，故总边数是 $O(n2^k)$ 的，从而总点数也是 $O(n2^k)$。再加入考虑立即返回的情形，它们从不立即返回的点集来，而且每个点在进入下一轮递归的时候两种抉择各至多送入一个点，所以这样的点集大小和也是 $O(n2^k)$ 的。所以整个搜索中出现的点集大小和是 $O(n2^k)$ 的，而搜索内部是线性的，所以整个做法的总复杂度是 $O(n2^k)$的。

这是一份严格按照上述描述写的代码

这是一份不严格按照上述描述写，使用了一些常数优化的代码

算法五

from skip2004, hehezhou

考虑一个点什么时候是叶子，就是他度数为一，此时其在一半询问中单独一个点为连通块。

而删叶子是很简单的事情，因此我们可以一个个剥叶子。

剥完叶子我们开始反着加，此时考虑一个点的父亲是谁。

一个点在另外一半不是孤立点时候的询问所在的连通块，一定包含了它的父亲。也容易说明这些连通块的交集中只有它的父亲。

此时只要做树上 $\log_2 n$ 个集合的交，其必定是其中一个集合顶部（深度最小的点），如果交唯一，一定是这些顶部深度最大的那个点。

时间复杂度 $O(n\log_2 n)$。

结合算法二，可以通过子任务 $1, 2, 4$。

结合算法三，可以通过本题。

Border 的第五种求法

idea, data, solution from he_____he

出题人在此谢罪。被意料之外的简单做法过了。

算法 1

简单清新 $O(n^2)$ 暴力。记 $\text{occ}$ 表示子串在原串中的出现次数。预处理每个区间的子串的 $\text{occ}$ ，然后对每个询问，暴力枚举 border 长度，统计答案即可。期望得分 $10$ 分。

算法 2

A 性质有什么用？可以发现，对两个不同位置，长度大于 $O(\log n)$ 且相等的区间，其代表的两个子串几乎一定不同！ 这说明 border 长度不超过 $O(\log n)$ ！我们只需枚举不超过 $O(\log n)$ 的长度即可。为了加快 $\text{occ}$ 的求值速度，可以选择建一个 SAM ，在枚举 border 长度的时候顺便在 SAM 的 DAG 上走，定位每个 border 所在的 SAM 节点。结合算法 1 ，期望得分 $20$ 分。

算法 3

要不，猜个结论？众所周知，一个区间的 border 能被分成 $O(\log n)$ 段等差数列。那么一个区间 border 的 $\text{occ}$ 有这个性质吗？遗憾的是，并没有。但是 $\text{occ}$ 实际上能被分成 $O(\sqrt n\log n)$ 段等差数列（证明先鸽着，说不定实际上是 $O(\sqrt n)$ ）。用基本子串字典求出 border 序列后寻找这些等差数列，在 $f_i=i$ 的时候即可求出答案。时间复杂度 $O(q\sqrt n\log n)$ ，结合算法 1,2 后，期望得分 $45$ 分。

算法 4

重新观察 border 的性质，我们回到最初的起点：找到所有 $1\leq i\leq r-l+1$ 使得 $s[l,l+i-1]$ 为 $s[1,r]$ 的后缀。那么我们可以找到 $s[l,l],s[l,l+1],\ldots,s[l,r]$ 在 SAM 的 DAG 上对应的链，答案即为这些点中作为 parent 树上 $s[1,r]$ 的祖先的那些点的 $\text{occ}$ 之和。

考虑该题中提到的 DAG 剖分，我们可以把链分成若干段重链上的区间。现在问题就相当于：每个 SAM 节点在 DAG 结构上有一个标号，有一个权值 $f_{\text{occ}}$ ，需要多次查询某个点到根的链上，某个区间的权值之和。等价于一个二维数点。共 $O(n)$ 个点，$O(q\log n)$ 次查询，总复杂度 $O(n\log n+q\log ^2n)$ ，期望得分 $100$ 分。

题外话

本题说明，我们能够将一个区间中所有 border 的信息定位到 SAM 节点上，相较于基本子串字典，我们虽然没有得到 border group 的表示，但我们得到了另一个角度的信息。或许我们以后能获得更有价值的信息？

面基之路

idea from he_____he, data,solution from hehezhou

算法一

首先需要注意到最重要的结论：题意等价于所有人走到同一位置所需最短时间。证明只需要让所有网友在面基成功之后跟随 hehe 蚤行动即可。

对于子任务 $1$，不难发现最终汇合点一定在某个点上或某条边正中。如果汇合点在边的非中点位置，移动到端点或中点，一定有一种更优。

只需要求出会合到每一个位置的答案即可。时间复杂度 $O(k(n\log n+m))$，期望得分 $30$。

算法二

对于子任务 $2$，不难发现 $T$ 就是最远点距离除以二。

首先会合时间不可能更早，因为 $1$ 和最远点的距离达到了 $2T$。而只需要让所有人移动到 $1$ 和最远点的带权中心就是一组合法方案。

算法三

首先汇合点在点上的情况是简单的，考虑汇合点在边上的情况。

定义边的左右侧是它的两个端点，枚举每个人是从哪一侧进入这条边的，每侧只需要考虑最晚进入的人即可，答案不难计算。

时间复杂度 $O(m2^k+kn\log n)$，期望得分 $85$。

算法四

由于每侧只需考虑最晚进入的人，对于每条边，一定存在一种最优方案，将所有人按照到达左侧时间排序后，一个前缀从左侧进入而剩余的后缀从右侧进入。

时间复杂度 $O(kn\log n+mk\log k)$，期望得分 $100$。

bonus

如果 hehe 蚤的速度是 $a$ 而网友们的速度是 $b$，这个问题又该怎么解决呢？

这个问题会在数日后被加入 uoj 题库。

机器人表演

idea, data from djq_cpp, solution from hehezhou

本题改编自 CPIdeas (https://codeforces.com/blog/entry/104374) 生成的题面：

You are given a string S consisting of 0 and 1. You can do the following operation on S any number of times: Choose a non empty substring T of S, and append 0 to the beginning and 1 to the end of T. The resulting string will be S again. How many different strings will S be after the operations? Find the count
modulo 998244353.

算法一

我会状压！

接下来令左括号对应 0，右括号对应 1，合法括号前缀是满足任意前缀 0 不少于 1 的串，合法括号串是 01 个数相等的合法括号前缀，$A$ 和 $B$ 可以合并出 $C$ 等价于 $C$ 可以被划分为两个子序列分别等于 $A$ 和 $B$。

首先我们考虑给定一个串 $T$，判断其是否可以通过合并串 $S$ 和某个括号串得到。这可以在 $O(|S||T|)$ 的时间内完成，具体的，设 $f_{i,j}(i\geq j)$ 表示是否存在一个合法括号前缀使得它和 $S[1:j]$ 可以合并出 $T[1:i]$。考虑转移，有以下两种转移：

1. $f_{i,j}\to f_{i+1,j+1} (S_{i+1}=T_{j+1})$

2. $f_{i,j}\to f_{i+1,j} (a_{i+1}\geq b_{j})$

其中若 $T_i$ 是左括号，$a_i=a_{i-1}+1$，否则 $a_i=a_{i-1}-1$，$b$ 是定义在 $S$ 上的类似序列。第一种转移显然正确，第二种转移是因为：所有合并方案中，合法括号前缀的两种数量都是固定的。

如果 $f_{|T|,|S|}=\text{true}$ 且 $a_{|T|}=b_{|S|}$，则串 $T$ 可以通过合并串 $S$ 和某个括号串得到。

对应这个 dp，我们可以列出求解原题的状压 dp。$dp_{i,j,V}$ 表示已经填好了 $T$ 的前 $i$ 位，$f_{i,k}$ 等于 $V$ 的第 $k$ 位，$a_i=j$，转移按照上述转移式对应转移即可。

时间复杂度 $O(2^nn(n+t)^2)$，可以通过子任务 $1,2,4$，期望得分 $45$。

如果省略无用状态，可以额外通过子任务 $3$，期望得分 $60$。

算法二

我是打表大师！我打表转移找到规律了！

规律就是：对于固定的 $S,i,j$，非零 $dp_{i,j,V}$ 两个后继状态的 $V$ 的最高位只和当前 $V$ 的最高位有关。

可以只记录 $V$ 的最高位，状态数减少为 $O(n(n+t)^2)$。

时间复杂度 $O(n^2(n+t)^2)$，进一步得到转移规律可以做到 $O(n(n+t)^2)$，期望得分 $75\sim 100$。

算法三

我喜欢严谨做题！我要证明这个结论！

先注意到几个重要性质：

1. 两个合法括号前缀合成的串一定是合法括号前缀。考虑定义不难得出。

2. 若 $f_{i,j}=1$，则有 $a_i\geq b_j$。考虑转移或考虑 dp 意义均不难得出。

考虑当前已经匹配了前 $i$ 位，$a_i$ 确定，并且可以匹配的 $S$ 的最长前缀是 $k$，考虑在算上第 $i+1$ 位 $x$ 以后，可以匹配的 $S$ 最长前缀：

1. $S_{k+1}=x$：显然新的最长前缀是 $k+1$。

2. 否则若 $x=0$（即左括号） 或 $a_i\gt b_k$：那么 $a_{i+1}\geq b_k$，新的最长前缀是 $k$。

3. 否则有 $x=1$（即右括号）且 $a_i=b_k$，这种情况较为复杂。先给出结论：新的最长前缀 $k'=\max_{t\lt k,b_{t}\lt b_k} t$。第一步证明这个前缀是合法的：不难发现 $S[k'+1,k]$ 是一个合法括号前缀，否则就存在更大的位置满足 $b_{t}\lt b_k$。首先证明 $f_{i,k'}=\text{true}$，只需要将 $f_{i,k}$ 对应的合法方案中，$S[k'+1,k]$ 对应的子序列划为合法括号前缀部分，由性质 $1$ 我们就得到了 $f_{i,k'}$ 对应的一组方案，因此 $f_{i,k'}=\text{true}$ 且可以转移到 $f_{i+1,k'}$。然后我们证明不存在更长的前缀 $x$ 可以匹配 $T$ 的前 $i+1$ 个位置，否则 $b_x\geq b_k\gt a_i-1=a_{i+1}$，与性质 $2$ 矛盾。

至此我们证明了这个结论。

期望得分 $100$ 分。

稳健型选手

idea,data,solution from xyr2005

谢罪！谢罪！谢罪！谢罪！谢罪！

算法一

我会暴力！状压当前剩下哪些数，复杂度 $O(n2^n+q)$，可以通过子任务一获得 $10$ 分。

算法二

我会观察性质！先考虑单组询问。

首先，如果 $n$ 是奇数，那 QAQ 蚤会在最后一次取最后一个数，转化成前 $n-1$ 个数的问题，容易发现这是最优的。所以我们可以假设 $2\mid n$。

考虑 QAQ 蚤取的数的集合要满足什么条件。令序列 $b_i=0/1$ 表示这个位置最终 QAQ 蚤 取不取。

那 QAQ 蚤可以贪心每次取 $b_i=1$ 的最靠前的那个，那么可以发现 一个 $b$ 合法当且仅当 $\sum b_i=\frac n2$ 且 $\forall i\in[1,n],\sum_{j=1}^ib_j\le \lceil\frac i2\rceil$

我们可以 $dp_{i,j}$ 表示考虑了前 $i$ 个元素，总共取了 $j$ 个，和最大是多少，转移时保证 $j\le \lceil\frac i2\rceil$ 即可。

复杂度 $O(n^2q)$ ，可以通过子任务一二获得 $20$ 分。

算法三

考虑优化算法二。

可以使用反悔贪心，从前往后扫，维护 QAQ 蚤取了哪些数。

每次加进来两个数 $x,y$，首先假设 $x,y$ 都取了，这时候取了的数的总数是 $\frac{i}2+1$，再删掉一个最小的已经取了的数。

用堆维护上述过程，复杂度 $O(nq\log n)$ ，可以通过子任务一二三获得 $40$ 分。

算法四

我们发现，前 $2i$ 个取了 $\le i$ 个 $\Leftrightarrow$ 后 $2i$ 个取了 $\ge i$ 个。

于是算法三也可以倒着来做，从后往前扫，维护 QAQ 蚤没取哪些数。

每次加进来两个数 $x,y$，首先假设 $x,y$ 都没取，这时候取了的数的总数是 $\frac i2-1$，再取一个最大的没取的数。

于是我们现在可以在 $O(\log n)$ 复杂度内，向前加两个数，向后加两个数，使用不删除莫队维护。

复杂度 $O(n\sqrt q\log n)$，可以通过子任务一二三四获得 $70$ 分。

使用压位trie/veb 维护，复杂度 $O(n\sqrt q\log_wn)/O(n\sqrt q\log\log n)$，期望得分 $70$ 分，实际得分 $100$ 分。

算法五

继续优化算法四。

使用分治，用主席树对 $[l,mid]$ 的每个后缀维护取了哪些数，对 $[mid+1,r]$ 的每个前缀维护没取哪些数。

然后考虑合并 $[x,mid]$ 和 $[mid+1,y]$，那会发生的变化是，$[x,mid]$ 中一些取了的数现在不取了，$[mid+1,y]$ 中一些没取的数现在取了。假设 $[x,mid]$ 中发生变化的数的集合是 $S$，$[mid+1,y]$ 中发生变化的数的集合是 $T$，那么 $|S|=|T|$ ， $\max S< \min T$，$S$ 是一段前缀，$T$ 是一段后缀。于是我们二分 $k$ ，找到最大的 $k$ 满足左边第 $k$ 小 $<$ 右边第 $k$ 大，然后就知道了 $S,T$，于是做完了。

复杂度 $O((n+q)\log^2n)$，可以通过子任务一二三四五获得 $100$ 分。

经过一周的准备， Public Judge 即将投入运营！

PJ Round #1 将在 2022 年 4 月 3 日 8:30 举行！比赛将进行 4.5 小时，共 3 道题，OI 赛制。难度可以近似为省选。

本次模拟赛的搬题人为 cdw, hehezhou ，组题人为 p_b_p_b 。另外，特别感谢 Qingyu 和其他所有参与者对 OJ 搭建和题源筛选做出的巨大贡献。

赛后会公开原题链接和题解链接。

参加本场比赛将有机会获得 pjudge 抱枕！获奖条件的 SHA256 为 bc082bd4ee6e645bccf44197d13a0da2d23138b26c67e37044859188305a7aed 。比赛结束后将公布条件。

特别提醒：本次比赛的题目均为原题，但为了比赛的公平性，请勿在比赛时尝试查找原题地址。如不幸见过原题，请向管理员报告。

欢迎加入 Public Judge 用户群（1009677675）。

OJ 的网址是 pjudge.ac。

后续通知将在群里发布，如果你有想提出的建议或是发现 OJ 的 bug，可以向 hehezhou 或 p_b_p_b 汇报。

upd: Round #1 结束啦

echo -n "没有 没有 没有 别想了" | sha256sum
bc082bd4ee6e645bccf44197d13a0da2d23138b26c67e37044859188305a7aed -

随机薅羊毛

idea, std from xuanyiming data, solution from hehezhou

算法一

我会 $n=2$！

设从 $1$ 号机开始的期望为 $x_1$，$2$ 号机开始的期望为 $x_2$。

如果 $1$ 号机抽奖失败，则接下来的过程就是从 $2$ 号机开始抽奖，反之同理。

因此 $x_1=(1-p_1)x_2+1, x_2=(1-p_2)x_1+1$。

解得 $x_1=\frac{2-p_1}{p_1+p_2-p_1p_2},x_2=\frac{2-p_2}{p_1+p_2-p_1p_2}$。

算法二

上面的方程组在 $n$ 更大的情况同样可以被列出来！

具体的，设从 $i$ 号机开始抽奖的期望是 $x_i$，那么有：

$$x_i=\frac{(1-p_i)\sum_{j\neq i}x_j}{n-1}+1$$

列出系数高消即可，时间复杂度 $O(n^3)$，期望得分 $40$。

算法三

令 $s=\sum_{i=1}^n x_i$，答案即为 $\frac{s}{n}$，那么上述方程可简化为：

$$x_i=\frac{(1-p_i)(s-x_i)}{n-1}+1$$

简单变形后化为：

$$x_i=\frac{(1-p_i)s+n-1}{n-p_i}$$

将 $n$ 个方程求和，整理得：

$$s=s\sum_{i=1}^n\frac{1-p_i}{n-p_i}+(n-1)\sum_{i=1}^n\frac{1}{n-p_i}$$

这是一个一元一次方程，简单求出系数即可。

时间复杂度 $O(n)$，期望得分 $100$ 分。

重构元宇宙

idea, std1, solution1 from vfleaking data, std2, solution2 from hehezhou

算法一

我会 $k=1$！

先确定 $0$ 号点的坐标为 $0$，找一个与 $0$ 号点距离非 $0$ 的点，不妨设为 $1$ 号点，令其坐标为 $d(0,1)$。

对于其他点，求出与这两个点的距离，即可简单分讨出坐标。

算法二

我会 $n=3$！

同样先确定两个点的坐标，简单解出第三点坐标即可。

算法三

考虑逐个点加入，同样令 $0$ 号点坐标均为 $0$，维护出当前这些点可以嵌入空间的最小维数 $k$ 以及一组坐标，同时维护一组含 $0$ 号点的大小为 $k+1$ 的点集 $\{x_i\}_{i=0}^k$，使得这个点集可以嵌入空间的最小维数同样为 $k$。

设当前加入点为 $x'$，考虑列出方程：

$$\sum_{i=0}^k(x_{t,i}-x'_i)^2=d^2(x',x_t)~~(t\in[1,k])$$

注意到 $d^2(0,x)=\sum x_i^2$，因此：

$$\sum_{i=0}^{k-1} x_{t,i} \cdot x'_i=-\frac{d^2(x',x_i)-d^2(0,x)-d^2(0,x_t)}{2}~~(t\in[1,k])$$

由于这个点集的性质，这 $k$ 个方程线性无关，可以使用高消唯一确定 $x'$ 的前 $k$ 维坐标。如果此时 $\sum_{i=0}^{k-1}x_i^{'2}\lt d^2(0,x')$，则说明空间的维数需要增加 $1$，简单的将 $x'_k$ 设为左右差的平方根，并将 $x'$ 加入点集即可。

时间复杂度 $O(n^4)$，交互次数不超过 $n(k+1)$，期望得分 $70$。

算法四

考虑维护出矩阵的逆，高消可以认为是将向量乘上逆矩阵。

每次计算出加入点集的新点后，相当于在原矩阵的下方增加了一行。新的逆矩阵可以在旧逆矩阵的基础上，以 $O(n^2)$ 的开销计算得到。

时间复杂度 $O(n^3)$，期望得分 $100$。

算法五

vfk 咕咕咕。

UPD: 更新了 https://vfleaking.blog.uoj.ac/blog/7612

磁球与磁棍

idea, solution from jacder, std, data from djq_cpp

算法一

暴力枚举删哪些边然后判。时间复杂度 $\tilde O(2^n)$，期望得分 $10$ 分。

算法二

考虑 DP。

令 $f[i][j][k][l]$ 表示子树 $i$ 被切成 $j$ 块，结点 $i$ 所在的连通块叶子深度均为 $k$，$i$ 和其父结点的连边情况是 $l$ 是否为合法的状态，转移可以直接树上背包。

时间复杂度 $O(n^2)$，期望得分 $40$ 分。

算法三

为了达到线性复杂度，我们需要将 $j$ 这一维优化掉。

对于原问题，容易发现当 $k < n$ 时，若存在切成 $k$ 个连通块的方案，则一定存在切成 $k+1$ 或 $k+2$ 个连通块的方案：称一个点是自由的当且仅当它的颜色与它所在连通块的叶子颜色不同，则此时必然存在一个自由的点；若它的度为 $2$，则可删两条边构造出 $k+2$ 的方案，否则可删一条边构造出 $k+1$ 的方案。

进一步地，若 $k \not= n - 3$，则要么有度数为 $2$ 的自由点，要么有至少两个度数大于等于 $3$ 的或一个度数大于等于 $4$ 的自由点。这些情况均可构造出 $k+2$ 的方案。而 $k = n - 1$ 必然无解。

这意味着可以直接令 $dp[i][j][k][l]$ 表示子树 $i$，子树内连通块数模 $2$ 余 $j$，根所在连通块叶子颜色为 $k$ 根和父结点连边状况为 $l$ 时子树内的最小连通块数，容易做到 $O(1)$ 转移。

std 中还原方案采用的方式是构造出最小值对应的方案再用上述的调整算法调整。直接用 dp 值自顶向下还原应该也是可行的，但需要一些讨论。

再见，辛丑！

转眼间，魔幻的 2021 就结束了，虎年到来了，vjudge 蜀汉的五虎上将跨越千年时空，前来 UOJ 庆祝新年，并注册为了 UOJ 用户 GuanYunChang, ZhangYiDe, ZhaoZiLong, MaMengQi, HuangHanSheng。

你将和这五位五虎上将一起，策划或参与各式各样的活动！

我们将于 $1$ 月 $30$ 日下午 13:00 到 18:00 举办一场 Goodbye Xinchou 比赛。比赛时间为 5 小时，共 5 道题。

赛制为 OI 赛制，有简单题也有有趣题，还有有趣的简单题，欢迎各位选手来玩！

再次提醒大家比赛中途只测样例，最后会进行最终测试，把所有提交记录重测。

赛制采取 OI 赛制，这也意味着只计入最后一次提交结果。这场比赛有很多有意思的题目，大家一定不要错过！

出题人：vfleaking, LMoliver, vectorwyx, orbitingflea, byqx, djq_cpp

这场成绩将计入 rating。

参加本次比赛将有机会获得 UOJ 抱枕！获奖条件的 SHA256 码为 6ca9cedbed07373bd30c7044928bd6c942babe696570b854af15df5e7d54c857。比赛结束后将公布条件。

UPD: 恭喜前5名的选手！

1. zhoukangyang
2. Itst
3. hos_lyric
4. csy2005
5. AKEE

echo -n "全场倒数第二个计入最终成绩的100分提交，如有多个取排名最高者。" | sha256sum
6ca9cedbed07373bd30c7044928bd6c942babe696570b854af15df5e7d54c857  -

恭喜 tzc_wk 获得 uoj 抱枕！

UOJ Sleep Round #1 将于 4 月 1 日星期七晚上 25：00 举行！比赛将进行 5 个小时，共三道题。

这是 UOJ 第一场 Sleep Round，入门及以上难度，欢迎大家来玩！

本场比赛的形式非常特殊，你需要在比赛开始前进入睡眠，并在梦中登录 UOJ 并报名。

题面，评测以及排行榜均只在 UOJ 梦境版可见。

出题人：he_____he, he_____hezhou, he_____hezhouzhendong

参加本次比赛将必定获得神秘小礼品！

再次提醒大家比赛中途只测样例，最后会进行最终测试，把所有提交记录重测。

UOJ Round #23 将于 12 月 18 日星期六晚上 19：00 举行！比赛将进行 3 个小时，共三道题。

这是 UOJ 第二十三场 UOJ Round，还是一如既往的省选及以上难度，欢迎大家来玩！

公元 1402 年 12 月 18 日，朱棣决定迁都北京。

最近，跳蚤国尝试迁都到跳蚤利亚，于是跳蚤国王找到了得力助手伏特。你能不能帮助伏特完成迁都工作呢？

出题人：skip2004, wlzhouzhuan, ezoilearner

参加本次比赛将有机会获得 UOJ 抱枕！获奖条件的 SHA256 码是 84808bd0172e35a9682af04f030495f72896874d93e36bc42cec26890fd1e7bd。比赛结束后将公布条件。

再次提醒大家比赛中途只测样例，最后会进行最终测试，把所有提交记录重测。

UPD：恭喜前五名的选手！

1. csy2005
2. qazswedx
3. peehs_moorhsum
4. AKEE
5. matthew99

echo "最终成绩写成形如'xxx-hh-mm-ss'的字符串，md5结果字典序最小的。" -n | sha256sum
84808bd0172e35a9682af04f030495f72896874d93e36bc42cec26890fd1e7bd  -

[ '028ea2ec5200d6828fbb0b087ea75b17', '090-01-40-59', '1092515503' ]
[ '042b302ca8efd8d55c5cd1c89e0a3ffc', '160-05-00-49', 'Rainbow_sjy' ]
[ '04b0caefef4f064293fb85182bd046e9', '220-02-56-46', 'qazswedx' ]
...

恭喜 1092515503 获得 uoj 抱枕！

写这篇博客的起因是校内模拟赛出重了。。然后 chenkuowen 用集合幂级数通过了，大为震撼。

首先对原图进行收缩，具体的，我们给每条边设置两个边权 $c, d$ 分别表示使这条边联通的方案数和使这条边断开的方案数，初始有边即为 $(1,1)$。

收缩含有三部分：缩一度点，缩二度点，叠合重边。

1. 缩一度点：删去这个点，并在答案上乘上 $c$。

2. 缩二度点：删去这个点，并合并两条边，具体的，$(c,d)=(c_ac_b,c_ad_b+d_ac_b)$。

3. 叠合重边：合并两条边，具体的，$(c,d)=(c_ac_b+c_ad_b+d_ac_b,d_ad_b)$。

做完以上操作后，每个点至少是三度点，并且 $m-n$ 不会增大。于是我们有 $m\geq \frac{3n}{2},m\leq n+k-1$，那么 $n\leq 2k-2$。

接下来考虑如何计算使这张图联通的方案数。

设 $f_S$ 表示点集 $S$ 的导出子图的联通生成子图个数，$g_S$ 表示点集 $S$ 的导出子图的生成子图个数。

那么

$$g_S=\sum_{\{P_k\}\in \text{part}(S)}\prod_{i=1}^k f_{P_i}\prod_{u\in P_i,v\in P_j,i\lt j} d_{u,v}$$

其中 $\{P_k\}\in \text{part}(S)$ 表示 $\{P_k\}$ 是 $S$ 的一个无序划分。

再设 $D_S=\prod_{u,v\in S} d_{u,v}$，那么有

$$\frac{g_S}{D_S}=\sum_{\{P_k\}\in \text{part}(S)}\prod_{i=1}^k \frac{f_{P_i}}{D_{P_i}}$$

注意如果有 $d_{u,v}=0$ 需要特殊处理（直接合并两个点）。

令 $G_S=\frac{g_S}{D_S},F_S=\frac{f_S}{D_S}$，上述式子实际上就是 $G=\sum_{i=0}\frac{F^i}{i!}=\exp(F)$。

所以 $F=\ln(G)$，注意到 $g_S=\prod_{u,v\in S} (c_{u,v}+d_{u,v})$，于是可以快速计算出 $F$。

时间复杂度 $\Theta(n+k^24^k)$。

首先作为管理员主要苦力向大家谢罪。这场比赛由于准备比较匆忙，以及管理员们的经验不足，导致部分分的分值和范围设置上有诸多不合理之处，样例与数据的强度也有较大差距，在此为造成大家不便表示歉意。

月球列车

idea from he_____he,mayaohua, solution from he_____he, data from hehezhou.

算法1

直接暴力模拟！时间复杂度 $O(nm)$ ，可以通过子任务 1，期望得分 $30$ 分。

算法2

考虑对于一次查询 $x$ ，依次决定每一个二进制位是 $0$ 还是 $1$ 。设 $a'_{j,i}=a_i \& (2^{j+1}-1)$ ，其中 $\&$ 表示二进制与。对于每个 $i$ ， $a_i+x$ 的 $2^j$ 位是 $a_i\oplus x$ 的 $2^j$ 位再异或上 $a_i+x$ 的第 $j-1$ 位是否进位。前者容易处理，后者等价于 $a'_{j-1,i}+(x\& (2^j-1))\geq 2^j$ 。所以求 $\bigoplus\limits_{i=1}^n (a_i+x)$ 的 $2^j$ 位时只需求出有多少个 $a'_{j-1,i}\geq 2^j- (x\& (2^j-1))$ 。可以排序预处理然后每次查询对每一位二分。

时间复杂度 $O((n+m)\log n\log a_i)$ ，可以通过前两个子任务，期望得分 $60$ 分。

算法3

注意到排序预处理的部分可以利用上一次排序的结果，将新的一位为 $0$ 的部分和为 $1$ 的部分归并排序，使预处理复杂度降至 $O(n\log a_i)$ 。

将查询离线之后，同样可以按上述方法将 $x$ 的前 $j-1$ 位的顺序用 $O(m\log a_i)$ 的复杂度求出。然后对于每一位，线性 two pointers 求出每个查询在这一位上的答案。

时间复杂度 $O((n+m)\log a_i)$ ，可以通过子任务 3，与算法 2 结合可以通过前三个子任务，期望得分 $90$ 分。

算法4

由于强制在线，我们不能预处理出所有查询的信息，但我们可以预处理出所有 $a_i$ 的信息。设对于 $j$ 预处理出的 $a'_{j,i}$ 的顺序为 $b_{j,1}\leq b_{j,2}\leq \cdots \leq b_{j,n}$ 。默认 $b_{j,0}=-\infty,b_{j,n+1}=\infty$ 。我们原先做的事就是将其中的一些 $+2^j$ 再和剩下的归并得到 $b_{j+1,1}\leq b_{j+1,2}\leq \cdots \leq b_{j+1,n}$ ，然后对于每个查询找到 $2^{j+1}-(x\& (2^{j+1}-1))$ 大于多少个 $b_{j,i}$ 。

此时多预处理出两个数组 $c_{j,i,0}=\max\{x|b_{j+1,x}\leq b_{j,i}\}$ 和 $c_{j,i,1}=\max\{x|b_{j+1,x}\leq b_{j,i}+2^j\}$ 。这个容易归并在 $O(n\log a_i)$ 内做到。

对于 $x$ 查询的时候如果求出 $2^{j+1}-(x\& (2^{j+1}-1))$ 在 $[b_{j,k},b_{j,k+1})$ 之间，那么直接用 $c_{j,k,0/1}$ 就可以得到 $j+1$ 的答案。这是因为 $\{b_{j+1}\}$ 中不存在 $(b_{j,k},b_{j,k+1})$ 中的数和 $(b_{j,k}+2^j,b_{j,k+1}+2^j)$ 中的数，$c_{j,k,0/1}$ 得到的解和 $2^{j+2}-x\& (2^{j+2}-1)$ 得到的解一定相同。

每次查询复杂度 $O(\log a_i)$ ，总复杂度 $O((n+m)\log a_i)$ ，可以通过所有子任务，期望得分 $100$ 分。

月球铁轨

idea from wangziji,he_____he, data,solution from hehezhou.

算法一

我会暴力！枚举每个区间再枚举每个位置的选择，然后排序求出第 $k$ 小。

复杂度 $O(2^nn^2)$，期望得分 $0$ 分。

算法二

定义 $f(x,T)=\max_{y\in T}(x\oplus y),g(x,T)=\min_{y\in T}(x\oplus y)$，其中 $x$ 是一个数，$T$ 是一个 $\mathbb{F}_2$ 上的线性空间。

考虑如何计算一个区间的最优稳定度。令 $c_i=a_i\oplus b_i(1\leq i\leq n)$。对于区间 $[l,r]$，求出 $x_{l,r}=\oplus_{i=l}^{r} a_i$，再对 $c_l\cdots c_r$ 求出张出的线性空间 $T_{l,r}$，则答案为 $f(x_{l,r},T_{l,r})$。

维护线性空间（可以维护一组基）以及求出 $f(x_{l,r},T_{l,r})$ 的复杂度均为 $O(m)$。

时间复杂度 $O(n^2m)$，可以通过子任务一，期望得分 $10$ 分。

算法三

我们发现如果一个区间的线性空间维数达到 $m$，则这个区间的答案就是 $2^m-1$。

随机数据下，维数小于 $m$ 的区间只有 $O(nm)$ 个，求出这些区间的答案后，使用经典算法求出第 $k$ 小即可。

时间复杂度 $O(nm^2)$，可以通过子任务三。

算法四

定义 $S_n=\oplus_{i=1}^n a_i$，则 $x_{l,r}=S_r\oplus S_{l-1}$。

对于性质 B，我们发现一个区间的答案就是 $S_r\oplus S_{l-1}$，于是我们把所有前缀异或和插入一颗 trie，然后 trie 上二分即可求出第 $k$ 小的答案。

时间复杂度 $O(nm)$，可以通过子任务四。

算法五

对于性质 C，此时区间 $[l,r]$ 答案就是 $f(0,T_{l,r})$。注意到一个性质，对于某个固定的 $l$，$T_{l,r}$ 最多只有 $m+1$ 种，维数分别为 $0\cdots m$，并且如果区间 $A$ 包含区间 $B$，$T_A$ 包含 $T_B$。

使用扫描线算法，每次在序列末尾加入一个数 $S_r$，并且维护出每个左端点当前对应的线性空间。加入一个数会使当前一个后缀的线性空间维数变大 $1$。维数变大总次数是 $O(nm)$ 的，于是暴力维护即可。

加粗部分更详细解释是，考虑使用 $S_{1}\cdots S_{r-1}$ 异或出 $S_r$，并且最小下标尽可能大，设这个最小下标是 $p$（如果不存在则为 $0$）。则 $p+1\cdots r$ 对应的 $T_{i,r}$ 维数均加一， $1\cdots p$ 对应的维数均不加一。

时间复杂度 $O(nm^2)$，可以通过子任务五。

算法六

我们发现一个性质，$f(x\oplus y, T)=f(x,T)\oplus g(y,T)$。于是区间 $[l,r]$ 的答案也是 $f(S_{l-1},T_{l,r})\oplus g(S_r,T_{l,r})$。

使用算法五维护出所有 $T_{i,r}$ 以及 $f(S_{i-1},T_{i,r})$。并且维护 $m+1$ 棵 trie，第 $t$ 棵 trie 包含 $f(S_{i-1},T_{i,r})(\texttt{dim}(T_{i,r})=t)$，其中 $\texttt{dim}$ 表示维数。

对于某个 $r$，$T_{i,r},g(S_r,T_{i,r})$ 同样最多 $m+1$ 种，且每一种对应一个维数。

于是计算出这几个值，并在对应 trie 上查询，但是这里有两个方向，一种是二分答案（逐位确定），每次跑一遍上述过程，时空复杂度分别为 $O(nm^3),O(nm)$，另一种是使用可持久化 trie 并多树二分，时空复杂度均为 $O(nm^2)$。

均可以通过子任务二，期望得分 $25\sim 70$ 分。

算法七

对于算法六的逐位确定方向，但是确定每一位的时候，通过 trie 的上一层，只维护出 trie 对应的一层。

时间复杂度 $O(nm^2)$，空间复杂度 $O(nm)$，可以通过本题，期望得分 $100$ 分。

月球车站

idea,solution from jiqimao, data from hehezhou.

以下把硬币的正反面属性称为颜色，0 表示背面，1 表示正面。

算法一

对于 $p=0$ 的情况，伏特永远不会翻转，因此当且仅当初始硬币全为正面，答案为 0，否则 skip 蚤也选择不操作答案为 -1。

可以通过子任务一，期望得分 $5$ 分。

算法二

对于 $p=1$ 的情况，伏特每次遇到背面的硬币都会将它翻转。

我们把同色的连续一些硬币称为一段。对于段数大于 $2$ 的局面，skip 蚤也只需要每次遇到正面的硬币都将它反转即可。容易发现这样即可让游戏无法结束。

当局面为全 0 或全 1，伏特显然获胜。

当局面为 00...011...1 时，显然伏特会获胜。

当局面为 11...100...0 时，伏特能否获胜与 1 的个数有关。当仅有一个 1 时，不管 skip 蚤如何操作，都会变为上述伏特必胜局面。否则，skip 蚤不翻转第一个 1 ，即可使段数大于 2 ，于是游戏无法结束。

判断一下即可，可以通过子任务二，期望得分 $10$ 分，结合算法一期望得分 $15$ 分。

算法三

规定一些记号：$c_x$ 表示局面 $x$ 的第一个硬币的颜色。$trans_{x,c}$ 表示局面 $x$ 去掉第一个硬币后接一个颜色为 $c$ 的硬币，即 $trans_{abcd,e}=bcde$。$f_x$ 表示局面 $x$ 的答案。

我们可以暴力地列一个 dp 出来。

若 $c_x=1$ ，$f_x=\max(f_{trans_{x,0}},f_{trans_{x,1}})+1$，

若 $c_x=0$，$f_x=pf_{trans_{x,1}}+(1-p)f_{trans_{x,0}}+1$。

这是个带环还带 $\max$ 的 dp，我们枚举 $\max$ 取值来源，每次用高斯消元求解。

特判掉 $p=1$ 或 $p=0$ 的情况之后若出现矩阵不满秩的情况则一定不合法。另外若求出的dp值不满足上述约束则也不合法。可以证明最多只有一种情况合法（因为最优策略唯一）。若没有合法情况输出 -1 ，否则输出唯一合法的解即可。

注意求解需先用 double 算出最优策略再算出取模后的答案。

复杂度为 $O(2^{2^{n-1}}\cdot2^{3n})$，可通过子任务三，期望得分 $10$ 分，结合算法一、二期望得分 $25$ 分。

算法四

为了进一步挖掘性质优化算法，先来研究一下两人都绝顶聪明时的这个博弈问题（伏特希望最小化步数，skip 蚤希望最大化步数）。

首先有一个很自然的问题：为什么 skip 蚤不是能翻就翻呢？其实是因为当 skip 蚤翻掉一个硬币时，他也就丧失了接下来对这个硬币的操作权。对于一个正面硬币，主动权掌握在 skip 蚤手中，而对于背面硬币，skip 蚤就陷入被动。

考虑到全正的局面是已知的最终局面，我们从这个局面开始推出其他局面的最优步数。

具体地，类似最短路的过程，我们维护一个队列，其中存储一些局面，它们已知最优步数且等待扩展其他局面。这些局面要按照最优步数从小到大排列。

从队头取出一个已经确定最优步数的局面 $z$ ，考察有哪些局面能一步转移到它，设为 $x,y$，其中 $c_x=0,c_y=1$。则如果 $x$ 是第一次被访问到，则 $x$ 的最优决策即可转移到 $z$。（伏特希望最小化步数）。类似的，如果 $y$ 是第二次被访问到，则 $y$ 的最优决策转移到 $z$。（skip 蚤希望最大化步数）

被扩展到的新局面存到队尾即可。

注意这里的 $x$ 和 $y$ 只有第一个硬币不同。则可以发现 $x$ 和 $y$ 总是同时被访问到，它们要第一次都是第一次，要第二次都是第二次。这样我们发现，每次都有且仅有一个局面可以扩展。

那么在一种理想的情况下，局面之间的转移关系就构成了一条链，所有局面的最优步数恰好取遍了 $0$ 到 $2^n-1$ 。

但是还有一个例外：当全正局面作为第二次访问到的 $y$ 出现时，它已经无法再被扩展了。此时还没有被扩展到的局面就是无解局面：以它们为初始局面的游戏无法结束。

选手们当然可以验证出在给定的数据范围内不存在这种例外情况。就算没有得到这个结论，也可以在代码中特判。当存在无解局面时，不管初始局面是否无解直接输出 -1 即可，这是因为在伏特随机的游走的时候，总会有可能走到无解局面。

下面还是证明一下在 $n$ 取任何值时都不会存在上述例外发生。即对于任何初始局面，伏特有必胜策略。

证明：我们把初始局面的硬币按 $1$ 到 $n$ 标号。从硬币按 $1$ 到 $n$ 排列到下一次硬币按 $1$ 到 $n$ 排列的一次过程称为一回合。对于每一回合，起初伏特看到背面的硬币就翻面，直到 skip 蚤第一次操作，伏特在这一回合之后就都不操作。

这样会发现每一轮过后局面表示的二进制数都会变小。总会变成全 0，此时伏特一路翻过去就获胜了。

证毕。

注意，上面的这个策略只是保证获胜的策略，并不是步数最少的策略。

于是，得到了这样的结论：局面之间的转移关系构成了一条链，所有局面的最优步数恰好取遍了 $0$ 到 $2^n-1$ 。我们可以按局面在这条链上的位置来给局面编号，局面 $i$ 的最优步数为 $i$，以下均使用这个标号描述局面。

回到最初的问题。当伏特操作与否随机时，利用这个结论来优化一下算法。

对于 skip 蚤，他从 $i$ 要么到 $i-1$，要么到某个 $x(x < i-1)$。对于伏特，他从 $i$ 要么到 $i-1$，要么到某个 $y(y > i-1)$。下面证明 skip 蚤每次都从 $i$ 到 $i-1$，即期望 $f_i$ 单调递增。

反证，若 $x < y,f_x > f_y$，则从 $y$ 到第一次到达 $x$ 的这些回合里，skip 蚤都从 $i$ 走到 $i-1$，那么必定经过 $x$。第一次到达 $x$ 之后按之前的最优策略走。则 $f'_y > f_x > f_y$，与最优性矛盾。则 $f_i$ 单调得证。

于是我们去掉了转移方程中的 $\max$，可以高斯消元解决，而观察方程组形态可以优化到 $O(2^{2n})$。

可以通过子任务三、四，期望得分 $40$ 分，结合算法一、二期望得分 $55$ 分。

算法五

观察到从局面 $i$ 一定会经过局面 $i-1$。我们改变状态定义：从 $i$ 到 $i-1$ 的期望步数。写出方程发现可以按链的顺序递推，优化为 $O(2^n)$。

期望得分 $100$ 分。

bonus: 是否可以在多项式复杂度内解决本题或得到局面序列的某一项。