好题题解整理（二）

发表于 2020-07-28 更新于 2021-03-29 分类于整理阅读次数：

没有摘要。

loj576 「LibreOJ NOI Round #2」签到游戏

有一个长为 \(n\) 的序列 \(\{B\}\) ，每次可以选一个区间 \([l, r]\) ，代价是 \(B\) 在该区间的 \(\gcd\) ，得到一个方程 \(\sum_{i=l}^k x_i = K\) ，要求花费最小的代价得到 \(n\) 个线性无关的方程。

\(q\) 次询问和修改，每次修改会修改 \(B\) 的一个位置的值。

时间复杂度：\(O(n\log+q\log^2)\) 。

题解

（未实现）

引理 1

存在最优解选择的每个区间满足 \(l=1 \lor r=n\) 且存在 \([1, n]\) 。

设 \(y_i = \sum_{j=1}^i x_j\) ，那么选择区间 \([l, r]\) 实质上是选择方程 \(y_r - y_{l-1} = K\) ，注意有 \(y_0 = 0\) 。

转换为图论问题，每个 \(y_i\) 是一个节点，一个方程是一条边，方程线性无关等价于图无环~~，那么这个问题本质上是求最小生成树~~。

在这个图论问题的基础上该引理是很自然的。定 \(0\) 为树根，把边定向，从父亲指向儿子，那么对于一条边 \(u \rightarrow v\) ，若 \(u < v\) 则把 \((u, v)\) 换成 \((0, v)\) ，否则换成 \((u, 0)\) 。容易发现每条边的代价不增，并且新图仍然是一颗树。此时每条边必然连向 \(0\) 或 \(n\) ，并且必然有边 \((0, n)\) 。

引理 2

存在最优解满足：存在参数 \(p\) 使得选择的区间由 \([1, n]\) ，\([1, i] (p \le i < n)\) 和 \([j, n] (1 < j \le p)\) 组成。

根据引理 1 ，由于选了 \([1, n]\) ，选前缀 \([1, i]\) 和选后缀 \([i + 1, n]\) 是等价的。那么最优解显然就是在每个 \([1, i]\) 和 \([i+1, n]\) 中选代价较小的一个，前者随 \(i\) 单调不增，后者随 \(i\) 单调不减。那么选前者的必然是一段后缀 \(i\) ，选后者的必然是一段前缀 \(i\) 。

正题

由引理 2 ，可以二分参数 \(p\) ，比较 \([1, p]\) 和 \([p, n]\) 的 gcd 大小进行判定。然后根据不同前后缀 gcd 的数量是 \(O(\log)\) 的，求答案枚举不同的 gcd 算贡献数量即可。

用线段树维护序列 \(B\) ，需要支持 \(O(\log)\) 的区间 gcd 查询或者把二分放在线段树上。具体细节不在讨论范围内。

zr1390 【五一省选集训day1】a

给定 \(k\) 次多项式 \(f(x) = \sum_{i=0}^k a_i x^i\) ，求多项式快速幂 \(f(x)^n \bmod x^m\) 的各项系数。

时间复杂度：\(O(mk)\) 。

题解

这应该算一个经典套路？

设 \(P(x) = f(x)^n = \sum_{i\ge{0}} b_i x^i\) ，对等式 \(P(x) f(x) = f(x)^{n+1}\) 两边求导，整理得到

\[P'(x) f(x) = n P(x) f'(x)\]

比较等式第 \(r\) 项系数，有

\[\sum_{i=0}^k a_i b_{r-i+1} (r-i+1) = n \sum_{i=1}^k a_i i b_{r-i+1}\]

上式就是 \(b\) 的递推式，\(O(mk)\) 递推出所有项即可。

th1691-a 最短路

\(n\) 个点的简单有向图，点有正权，找一个权值和最小的导出子图满足 \(1\) 和 \(n\) 相互可达，求最小权值和。

时间复杂度：\(O(n^3)\) 。

题解

对于一个合法的导出子图，把任意一条从 \(1\) 到 \(n\) 的简单路径称为主路径。由于要满足 \(n\) 可以到达 \(1\) ，主路径上会挂一些往回走的路径，称为回溯路径，如下图所示：

底下的直线是主路径，上面的弧线是回溯路径，称一个回溯路径的起点和终点分别为 A 类点和 B 类点，可以发现存在最优解主路径上只考虑 \(n\) 以外的这两类点的话，它们交替出现。

据此可以设计 DP ，状态内只需要考虑主路径最后两个特殊点，转移就是最短路的松弛。两种状态 \(f_{i,j}, g_{i,j}\) 的意义如下两图：

bz2560 串珠子

有 \(n\) 个点的无向图，第 \(i\) 个点和第 \(j\) 个点之间有 \(c_{i,j}\) 条无向边，求简单连通子图数目。

时间复杂度：\(O(2^n n^2)\) 。

题解

（未实现）

设集合幂级数 \(f_S\) 表示只点集 \(S\) 的导出子图的连通子图数目。连通的限制很强，考虑忽略限制得到类似的集合幂级数 \(g\) ，然后反演。对于 \(g_S (S \neq \varnothing)\)，枚举任意一个点所在连通块，有

\[\forall x \in S, g_S = \sum_{x\in{T} \land T \subset S} f_T g_{S \setminus T}\]

从这个式子直接做就是 \(O(3^n)\) 的，但是注意到这很能和子集卷积扯上关系，如果把每个上式枚举每个 \(x\) 累加，可以得到

\[|S| g_S = \sum_{T \subset S} |T| f_T g_{S \setminus T}\]

另设两个集合幂级数 \(F_S = |S| f_S\) 和 \(G_S = |S| g_S\) ，上式即 \(G = F \times g\) ，于是

\[F = \frac{G}{g}\]

利用集合幂级数的占位多项式科技即可。

事实上 \(F\) 就是 \(f\) 这个集合幂级数求导的结果，上式两边积分，还可以得到 \(f = 1 + \ln g\) ，加 \(1\) 是因为求导再积分损失了常数项。

从另一个角度考虑，反演那一步改成枚举实际连通块数量，就有 \(g = \sum_{i\ge{0}} \frac{(f-1)^i}{i!} = e^{f-1}\) ，减一是因为实际连通块不能算空的。

th1691-c 集合操作

给定一个长为 \(n\) 的数组 \(a\) 和 \(n\) 个下标集合，第 \(i\) 个集合 \(S_i\) 初始只有一个元素 \(i\) 。

定义 \(F(S, i) = \sum_{j\in{S}} [a_i = a_j]\) ，以及 \(G(S, k) = \sum_{i\in{S}} \sum_{j\in{S}} [F(S, i) + F(S, j) \le k]\) ，要求维护两种操作（一共 \(n\) 次）：

给定 \(i, j\) 令 \(S_i \leftarrow S_i \cup S_j, S_j \leftarrow \varnothing\) 。
给定 \(i, l, r, k\) 求 \(G(S_i \cap [l, r], k)\) 。

时间复杂度：\(O(n^{\frac{5}{3}})\) 。

题解

（未实现）

问题 1

只有一个不变的下标集合 \(S\) ，每次询问给定 \(l, r, k\) 求 \(G(S \cap [l, r], k)\) 。

对于一个询问，设 \(T = S \cap [l, r]\) ，构造序列 \(b\) 满足 \(b_i = \sum_{j\in{T}} [a_j=i]\) ，那么不难发现答案实际上是 \(\sum_{i} \sum_{j} b_i b_j [b_i + b_j \le k]\) 。

注意到 \(\sum_i b_i = O(n)\) ，因此 \(b\) 不同的取值只有 \(O(\sqrt{n})\) 种，把相同的取值放一起考虑，双指针一下就可以 \(O(\sqrt{n})\) 处理。那么问题转换为怎么维护这个 \(b\) ，\(T\) 中每个元素对 \(b\) 的影响是 \(O(1)\) 的，因此使用莫队处理询问即可。

问题 2

只有一个下标集合 \(S\) ，每次询问给定 \(l, r, k\) 求 \(G(S \cap [l, r], k)\) ，每次修改在 \(S\) 中添加一个新的下标 \(i\) 。

在问题 1 的基础上要支持插入一个元素。不难想到带修莫队，每次插入就是时间轴的一个移动，容易发现时间轴的一次移动对 \(b\) 的影响也是 \(O(1)\) 的。

问题 3

有若干不变的下标集合 \(S_i\) ，每次询问给定 \(i, l, r, k\) 求 \(G(S_i \cap [l, r], k)\) 。

沿用问题 1 的解决思路，对每个集合单独开一个莫队显然不行，注意到 \(\sum_i |S_i| = O(n)\) ，不妨考虑阈值分块，称 \(|S_i| \le n^{\frac{2}{3}}\) 的为小集合，反之为大集合。对于小集合的每个询问，线性地求出答案，对于大集合沿用莫队，由于大集合只有 \(O(\sqrt[3]{n})\) 个，询问总数是 \(O(n)\) ，可以证明莫队总复杂度是 \(O(n^{\frac{5}{3}})\) 而不是看上去的 \(O(n^{\frac{11}{6}})\) 。复杂度分析时应该注意普通莫队的复杂度事实上是 \(O(n\sqrt{q})\) ，而且 \(\sqrt{q}\) 是个凹函数。

问题 4

有若干下标集合 \(S_i\) ，每次询问给定 \(i, l, r, k\) 求 \(G(S_i \cap [l, r], k)\) ，每次修改在 \(S_i\) 中添加一个新的下标 \(j\) 。

在问题 3 的基础上会多一些情况。小集合可能变成大集合，可能前一段时间暴力算后一段时间莫队，不影响复杂度。大集合添加元素时，沿用问题 2 的思路，应该使用带修莫队。注意到询问总数是 \(O(n)\) 的，因此所有大集合的时间轴长度和是 \(O(n)\) 的。这里的带修莫队可能会比较复杂，但不会增加复杂度。一个可行的做法是每次时间轴的长度达到 \(O(n^{\frac{2}{3}})\) 时就把莫队的答案跑出来，然后把时间轴清理掉。这个复杂度和问题 3 的复杂度分析一致。

正题

好了，通过层层递进已经得到了弱化问题的解法。那么对于完整的问题，无非就是把插入元素换成了合并集合，容易想到启发式合并，那么本质上仍然是插入。但是插入的次数并不是 \(O(n)\) 的，它带个 \(\log\) 。乍一看这个复杂度分析爆了，但实际上是不会变的，因为集合的大小和始终是 \(O(n)\) 的，时间轴的清理次数仍然是 \(O(\sqrt[3]{n})\) 而并非看上去的 \(O(\sqrt[3]{n}\log)\) 。

~~不愧是 lxl 出的数据结构题。~~

uoj21 【UR #1】缩进优化

一份 \(n\) 行的代码，第 \(i\) 行有 \(a_i\) (\(a_i \le M\)) 个空格作为缩进，要求确定一个 Tab 宽度 \(x\) 使得每一行尽量把空格替换成 Tab 后字符总数最小。

时间复杂度；\(O(n+M\log{M})\) 。

题解

（未实现）

降智好题？

不难发现问题等价于最大化 \(\sum_{i=1}^n \lfloor \frac{a_i}{x} \rfloor (x - 1)\) 。碰到这个整除第一反应可能是整除分块，于是可以得到一个 \(O(M+n\sqrt{M})\) 的做法。

然而不妨枚举答案 \(x\) ，可以发现整除的值的上界是 \(\lfloor \frac{M}{x} \rfloor\) ，此时可以枚举每个可能的值算贡献，复杂度是调和级数。

这告诉我们，当对多个数分别进行整除分块算贡献的时候，可以结合到一起转换为调和级数的复杂度。

loj6400 yww 与连通块计数

给定一颗 \(n\) 个节点的树，每个点有点权，称一个连通块是合法的当且仅当其点权的 gcd 和 lcm 分别为 \(P, Q\) ，求合法连通块数目。所有点权没有平方因子，且质因子不超过 50 。

时间复杂度；\(O(2^w n)\) ，其中 \(w\) 是点权的质因子数目。

题解

（未实现）

由于点权没有平方因子，事实上可以把点权看成一个集合，那么一个连通块合法的条件可以转换为点权交为空集，点权并为全集。把集合看成 \(w\) 位二进制数，这个条件也等价于每个二进制位在连通块中同时存在点权为 0 的点和点权为 1 的点。

到这里做法其实很多。一个容易理解的做法是子集容斥，注意到一个二进制位同时存在 0 和 1 是较难计算的，但是其否定形式，一个二进制位的数全部相同，这个条件是很好处理的。设 \(f_S\) 表示钦定 \(S\) 二进制位为 1 的位置必须满足所有点权全部相同的连通块数目。那么答案就是

\[\sum_{S} f_S (-1)^{|S|}\]

而每次计算一个 \(f_S\) 显然可以只需要考虑每个点权在 \(S\) 上的取值，那么在这种意义下一个连通块是合法的当且仅当所有点权相同。那么只把相同点权的两个相邻点连边，问题转换为求一个森林的连通块数目，这就很朴素了，线性 DP 即可。

loj6399 yww 与魔法阵

给定长 \(n\) 的一个 01 构成的三角形，求一个子三角形满足边界位置都是 0 且面积最大。这里三角形就长这样子：

时间复杂度；\(O(n^2)\) 。

题解

子三角形的数目是 \(O(n^3)\) 的，显然无法显式地一一枚举~~（甚至不能隐式地一一枚举）~~。事实上由于只是需要最大化面积没有必要考虑到每个子三角形。考虑增量法，对于当前的最优面积 \(S\) ，只需要考虑面积超过 \(S\) 的子三角形。

从下到上枚举，枚举每一个点作为子三角形的最上方顶点考虑更新答案。只需要判断是否存在子三角形比当前面积大。经过一些预处理后可以 \(O(1)\) 检查。预处理的东西有点多，这里略去。

显然答案的增长次数是 \(O(n)\) 的。

cf1349d Slime and Biscuits

有 \(n\) 个人，第 \(i\) 个人一开始有 \(a_i\) 个石头（\(\sum_{i=1}^n a_i = m\)）。每一轮依次执行如下两个操作直到有一个人拥有 \(m\) 个石头：

在 \(m\) 个石头中随机选择一个，设该石头的所有者为 \(i\) ，在 \(i\) 除外的 \(n-1\) 个人中随机选择一个 \(j\) ，把该石头从 \(i\) 移动到 \(j\) 。

求期望轮数。

时间复杂度：\(O(n+m)\) 。

题解

若第 \(i\) 个人拥有 \(m\) 个石头，则称游戏停留于 \(i\) 。

设 \(f_i\) 表示第 \(i\) 个位置对答案的贡献，也就是答案的期望中停留在第 \(i\) 个位置的组成部分。严格来讲是一个条件期望，是在停留于 \(i\) 的条件下的期望轮数乘上停留于 \(i\) 的概率。那么根据 \(f\) 的定义容易知道答案即 \(\sum_{i=1}^n f_i\) 。

但是直接计算 \(f_i\) 是困难的，因为要停留于 \(i\) ，最难以处理的限制是停留于 \(i\) 之前不能在任何位置停留。不妨忽略该限制，让游戏无休止的进行，设 \(g_i\) 表示第一次停留于 \(i\) 时的轮数的期望。考虑两者关系，枚举第一次停留的位置 \(j\) ，有

\[g_i = \sum_{j=1}^n (f_j + A_{j,i} p_j)\]

其中 \(p_j\) 表示第一次停留的位置恰好是 \(j\) 的概率，\(A_{j,i}\) 表示把停留于 \(j\) 作为初始状态，到第一次停留于 \(i\) 经过的轮数的期望。

考虑计算 \(g_i\) ，此时只需要关注第 \(i\) 个人拥有的石头，不难发现其他的石头不管在谁手里都是没有区别的，那么 \(g_i\) 的值只和 \(a_i\) 有关，不妨构造 \(h\) 满足 \(h_{a_i} = g_i\) ，而计算 \(h\) 是很简单的，可以线性消元解出，或者差分后直接递推。

然后考虑计算 \(A\) ，不难发现 \(i \neq j\) 时有 \(A_{j,i} = h_0\) ，反之有 \(A_{i,i} = 0\) 。

那么只需要计算出 \(p\) 就可以得到 \(f\) 了，可惜 \(p\) 是很难计算的，但是注意到我们并不需要关注 \(f\) 具体的值，只需要知道 \(\sum f_i\) ，另外尽管无法求出 \(p\) ，但是可以知道有 \(\sum p_i = 1\) 。到这里不难想到把上式求和，得到

\[\sum g_i = n \sum f_i + (n - 1) h_0\]

bz2688 Green Hackenbush

两个人轮流在一棵树上删边，每次删边后不与根联通的子树直接被删去，不能删边的游戏者输。

现有 \(n\) 棵树，第 \(i\) 棵树是含有 \(a_i\) 个节点的二叉树（从 \(C_{a_i}\) 个里面随机选一个）。求先手必胜概率。

时间复杂度：\(O(n^4)\) 。

题解

如何得到一棵树的 SG 值？

如果根的度数恰为 0 ，SG 值显然为 0 。

如果根的度数恰为 1 ，设与根相连的点为 \(u\) ，设 \(u\) 的子树对应的 SG 值为 \(k\) ，不难发现原树的 SG 值即 \(k+1\) 。

如果根的度数大于 1 ，那么可以把根“分裂”，把原树拆成一个森林，每个森林的根的度数都恰好为 1 。容易发现这个森林与原树等价，那么应用 SG 定理，原树的 SG 值就是每个子树的 SG 值加一的异或和。

然后就可以 DP 求解了，设 \(f_{i,j}\) 表示 \(i\) 个节点的二叉树中 SG 值为 \(j\) 的概率。然后合并答案就利用 SG 定理和背包合并即可。

cf1067e Random Forest Rank

给定一颗 \(n\) 个节点的树，随机生成一个子图，每条边都有 \(\frac{1}{2}\) 的概率出现，求该子图的邻接矩阵的秩的期望。

时间复杂度：\(O(n)\) 。

题解

引理 1

一颗树的邻接矩阵的秩就是其最大匹配数的两倍。

咕咕咕。

引理 2

一个森林的邻接矩阵的秩就是其最大匹配数的两倍。

显然如果图有多个连通块，其邻接矩阵的秩就是每个连通块的邻接矩阵的秩的和。那么根据引理 1 不难推广到引理 2 。

正题

有了引理 2 就能直接 DP 了。首先树的最大匹配基于一个贪心：选一个根，然后每个子树分别匹配，如果有一个儿子是非匹配点，就把当前节点与该节点匹配。森林的话是类似的。朴素的一个 DP 是设 \(f_{u,0/1}, g_{u,0/1}\) 什么的，边匹配边计数，但这里有个更简洁巧妙的 DP 设计。

设 \(f_u\) 表示在上述贪心过程中 \(u\) 与一个儿子匹配的概率，把每个匹配的贡献算在父亲上，不难发现答案就是 \(\sum 2f_u\) 。转移计算 \(u\) 无法与儿子匹配的概率，此时 \(u\) 的每个儿子 \(v\) 对“无法匹配”这个事件而言是独立的，有

\[f_u = 1 - \sum_v (\frac{1}{2} + \frac{1}{2} f_v)\]

th1693-b 组合数问题

给定 \(n, m\) 求 \(\sum_{i=0}^{n}(-1)^{i} \sum_{j=0}^{n} j^{m} \binom{j}{i} (m+i)^{j}\) 。

时间复杂度：\(O(n\log m)\) 。

题解

式子那么长唬你的，交换求和顺序，原式即

\[\sum_{j=0}^{n} j^{m} \sum_{i=0}^{j} (-1)^{i} \binom{j}{i} (m+i)^{j}\]

二项式定理展开后面的幂次，原式即

\[\sum_{j=0}^{n} j^{m} \sum_{k=0}^{j} \binom{j}{k} m^{j-k} \sum_{i=0}^{j} (-1)^{i} \binom{j}{i} i^{k}\]

看上去式子变复杂了，问题不大，因为最后一个求和符号里头的式子很友好，看上去很像第二类斯特林数的通项公式：

\[\genfrac\{\}{0pt}{}{k}{j} = \frac{1}{j!} \sum_{i=0}^j (-1)^{j-i} \binom{j}{i} i^k\]

代入，原式等于

\[\sum_{j=0}^{n} j^{m} \sum_{k=0}^{j} \binom{j}{k} m^{j-k} \genfrac\{\}{0pt}{}{k}{j} j! (-1)^j\]

然后会发现 \(k\) 枚举了个寂寞，\(k < j\) 时这个斯特林数都没有值，直接令 \(k=j\) ，于是原式等于

\[\sum_{j=0}^{n} j^{m} j! (-1)^j\]

虽然不难，但还是很妙，原式后面 \((m+i)^j\) 这个幂次替换成任意 \((K+i)^j\) 都不会影响答案，\(m\) 的贡献仅仅在于 \(j^m\) 。一旦发现这个巧妙的性质问题就很明了了。

th1693-c 三角形

给定一个点数 \(N \times M\) 的网格图，求有多少定点都在格点上的三角形，满足三角形区域内（包括边上）只有恰好 3 个格点。

时间复杂度：\(O(N^{\frac{2}{3}} + M^{\frac{2}{3}})\) 。

题解

要统计的三角形可以分为以下两类：

Pick 定理

一个顶点都在个点上的多边形的面积恰好为 \(a + \frac{b}{2} - 1\) ，其中 \(a, b\) 分别是多边形内部的格点数和边上的格点数。

引理 1

一个顶点在格点上的三角形只在区域内有恰好三个个点当且仅当其面积为 \(\frac{1}{2}\) 。

必要性：直接套用 pick 定理，有 \(a=0,b=3\) ，面积就是 \(\frac{1}{2}\) 。

充分性：还是套用 pick 定理，有 \(a + \frac{b}{2} - 1 = \frac{1}{2} \land a \ge 0 \land b \ge 3\) ，容易解出恰有 \(a=0,b=3\) 。

引理 2

第二类三角形面积始终不为二分之一。

不妨设上图的左下右上坐标分别为 \((0, 0), (n, m)\) ，另外两个顶点坐标分别为 \((a, m), (n, b)\) ，那么三角形面积即 \(\frac{nm-ab}{2}\) 。应用反证法，若面积恰为二分之一则 \(ab=nm-1\) 。由于 \(ab < am < nm\) ，那么 \(ab \le nm - 2\) ，矛盾。

引理 3

在确定对角线的前提下，使得第一类三角形面积恰为二分之一的合法的第三个顶点不超过一个，并且当且仅当对角线上没有其他格点时存在一个合法第三顶点。

不妨设上图的左下右上坐标分别为 \((0, 0), (n, m)\) ，第三个顶点坐标 \((a, b)\) ，那么有 \(am - bn = 1\) ，根据不定方程那一套理论，方程有解当且仅当 \(n \bot m\) ，并且对于任意一组解 \((a_0, b_0)\) ，所有解都可以表示为 \((a_0 + kn, b_0 + km)\) 。

~~接下来证明 \(n \bot m\) 时恰有一组合法解。~~这部分咕了。

正题

需要注意第一类三角形有一些对称的情况，只考虑上图中的一种然后乘 4 即可。那么根据三个引理，答案就是

\[4 \sum_{i=1}^N \sum_{j=1}^M (N - i) (M - j) [i \bot j]\]

到这里终于转换为数论问题，看到互质无脑莫反，得到原式等于

\[4 \sum_{k\ge{1}} \mu(k) \sum_{i=1}^{N/k} \sum_{j=1}^{M/k} (N - ik) (M - jk)\]

注意到 \((\lfloor \frac{N}{k} \rfloor, \lfloor \frac{M}{k} \rfloor)\) 的值只有 \(O(\sqrt{N} + \sqrt{M})\) 种，枚举每一种算答案，不难发现只要杜教筛筛出 \(\mu(k), \mu(k)k, \mu(k)k^2\) 三个函数的前缀和即可。

这玩意应该叫。。。双关键字整除分块？

lg5284 [十二省联考2019] 字符串问题

给定字符串 \(S\) 。有 \(n\) 个 A 类子串~~（可以加五分）~~和 \(m\) 个 B 类子串，每个 A 类子串有个支配集合，由 B 类子串构成。支配集合的大小总和不超过 \(k\) 。

求一个长度最大的串 \(T\) ，使得存在一个分割 \(T = t_1 + t_2 + t_3 + ... + t_p\) ，满足：

\(\forall 1 \le i \le p\) ，\(t_i\) 是 A 类子串。
\(\forall 1 \le i < p\) ，存在 B 类子串 \(r\) 属于 \(t_i\) 的支配集合，使得 \(r\) 是 \(t_{i+1}\) 的前缀。

时间复杂度：\(O(|S|+(n+m)\log+k)\) （这里认为字符集大小为 \(O(1)\)）。

题解

（未实现）

容易想到转换为图论问题，把所有 A 类子串和 B 类子串看做一个节点，A 类子串的出边集合就是其支配集合，B 类子串的出边集合就是它作为前缀出现的 A 类子串集合。

定义 A 类子串的权值为其长度，B 类子串的权值为 0 ，那么问题就是在这张有向图上求最长路（不一定是简单路）。由于权值都是非负且不存在零环，只要有环 \(T\) 的长度就可以是无穷大。而没有环的时候它是张 DAG ，直接 DP 求最长路即可。

看起来做完了，然而有一个问题，可以发现 B 类子串的出边集合大小是 \(O(n)\) 的，这张图的边数是 \(O(nm)\) 的。

后缀树优化建图

搞个标题看起来逼格一些，咱不会后缀树，还是用 SAM 吧。

注意到 B 类子串 \(q\) 向 A 类子串 \(r\) 有边当且仅当 \(q\) 是 \(r\) 前缀，也就是前者的反串是后者的后缀。而所有节点都是 \(S\) 的子串，不妨对 \(S\) 的反串建 SAM ，那么此时有边的条件就是在 parent 树上 \(r\) 在 \(q\) 的子树内。那就好办了，利用 parent 树优化建图，但是要考虑到只有 B 类串向 A 类串连边，直接建图会产生 A 类串到 A 类串或者 B 到 B 的不合法边。另外 SAM 的一个节点代表了多个子串，为了避免连出自环的情况可能需要额外拆点（舍弃了 SAM 最简的性质）。

cf102465j(gym) Mona Lisa

有四个随机数生成器 \(A, B, C, D\) ，每次可以从一个随机数生成器中等概率获得一个 \([0, 2^n)\) 的整数。要求分别从四个生成器获得整数 \(a, b, c, d\) 满足 \(a \oplus b \oplus c \oplus d = 0\) 。

时间复杂度：\(O(2^{\frac{n}{3}})\) 。

题解

生日悖论

表述一：对于两个长度为 \(O(\sqrt{n})\) 而值域 \(O(n)\) 的随机数列，它们的交集的大小的期望是 \(O(1)\) 的。

表述二：对于两个长度为 \(O(n)\) 而值域 \(O(n)\) 的随机数列，它们的交集的大小的期望是 \(O(n)\) 的。

正题

这种类似于碰撞的东西往往就要考虑生日悖论，生日悖论总能带来很好的效果。

对于每个随机数生成器，分别取 \(O(2^{n/3})\) 个元素得到集合 \(S_a, S_b, S_c, S_d\) 。然后称前 \(\frac{n}{3}\) 个二进制位为关键位，找到 \(S_a, S_b\) 中关键位异或为 0 的值，并把它们的异或和加入集合 \(P\) ，那么 \(P\) 的每个元素在关键位上的取值都是 0 。对 \(S_c, S_d\) 做同样的处理得到 \(Q\) 。

根据生日悖论的表述二，\(P, Q\) 的大小的期望都是 \(O(2^{n/3})\) 。

接下来在 \(P, Q\) 中分别找到两个元素 \(x, y\) 满足 \(x \oplus y = 0\) ，这样的 \(x, y\) 就对应一组解。事实上就是求 \(P \cap Q\) ，注意到由于 \(P, Q\) 的元素只在 \(\frac{2n}{3}\) 个非关键位上有值，可以认为它们是值域范围 \(2^{2n/3}\) 的随机数，那么根据生日悖论的表述一，它们交集的大小期望是 \(O(1)\) 的。

nowcoder6766-a 等级之题 N1（8.3）

初始时有 \(n\) 个黑球和 \(m\) 个蓝球。进行 \(k\) 轮操作，每一轮操作如下：

有 \(p\) 的概率添加一个黑球，有 \(1-p\) 的概率添加一个蓝球。
从所有球中随机扔掉一个球。

求最后黑球的数量的期望。

时间复杂度：\(O(\log k)\) 。

题解

容易发现操作不会改变球数，设 \(N = n + m + 1\) 。容易想到设 \(f_{i,x}\) 表示 \(i\) 轮操作后黑球数量为 \(x\) 的概率然后 DP 。那么 \(f_{i,x}\) 有 \(P_{x,-} = \frac{x}{N}(1-p)\) 的概率转移到 \(f_{i+1,x-1}\) ，有 \(P_{x,+} = \frac{N-x-1}{N}p\) 的概率转移到 \(f_{i+1,x+1}\) 。

设 \(i\) 轮操作后的黑球期望 \(E_i = \sum_{x=0}^N f_{i,x} x\) 。然后考虑 \(f_{i,x}\) 在一轮转移中对期望值的贡献，有 \(P_{x,-}\) 的概率减一，\(P_{x,+}\) 的概率加一，这部分期望的改变量就是 \(P_{x,+} - P_{x,-} = \frac{N-1}{N}p - \frac{x}{N}\) 。

为了方便，设 \(a = \frac{N-1}{N}\) ，有

\[E_{i+1} = E_i + \sum_{x=0}^N f_{i,x} (ap - \frac{x}{N}) = E_i + ap - \sum_{x=0}^N f_{i,x} \frac{x}{N} = a(p+E_i)\]

妙啊，迭代一下这个递推式就可以快速幂了，最后整理可以得到

\[E_k = a^k E_0 + p (N-1) (1 - a^k)\]