前言

难度：CF 2600-2700（有一道是 2500）

别问我为啥没有 1 到 5。

\(\color{blueviolet}{CF1473F}\)

此题是坏题，他卡你空间。

每一个元素有选或不选两种状态，并且有依赖项，元素的贡献有正负，数据范围不大，可以自然联系到最大权闭合子图，采用最小割模型。

建模方式如下：

对于一个正权点 \(u\)，连边 \(S \to u\)，容量为 \(b_i\)。
对于一个负权点 \(u\)，连边 \(u \to T\)，容量为 \(-b_i\)。
对于所有 \(i\)，对于其所有依赖的 \(j\) 连边，容量为正无穷。

但这样建边空间就爆炸了，考虑到值域很小，一个数不同约数个数不会很多。对于一个数 \(a_i\)，枚举其约数 \(x\)，对于每一个 \(x\) 只需要向最近的 \(x\) 建边即可，这样由于依赖关系的传递性不会出问题。

现在考虑最小割的意义，对于源点到正权点的一条边流满表示这个点我们舍弃掉了，对于负权点到汇点的边流满表示这个点我们被迫选择了，所以有答案 \(\left( \sum \limits _ {b_i > 0} b_i \right) - f\)，其中 \(f\) 为最小割。

\(\color{blueviolet}{CF1511F}\)

此题是神仙题。

先建 Trie 树，设 \(f_{i, u, v}\) 到第 \(i\) 个字符，两个分割分别处在 \(u\) 节点与 \(v\) 节点的方案数。

暴力转移是简单的，数据范围提醒我们要用矩阵优化，对于一个状态（有序数对）\((u, v)\) 建立一个点，若状态 \((u, v)\) 可以向 \((u', v')\) 转移，则在代表两个状态的点之间连边。

特殊地，若 \(u'\) 是终止节点，则 \((u', v')\) 同时具有 \((0, v')\) 的转移，\(v'\) 也同理；若 \(u', v'\) 都是终止节点，状态 \((u', v')\) 同时具有 \((0, 0)\) 的转移。

所以对于上述情况，\((u, v)\) 也可以向 \((u', v')\) 的等价状态连一条边，于是我们得到了一个有向图，等价于让我们求长度为 \(m\) 的从 \((0, 0)\) 到 \((0, 0)\) 路径条数，但此时状态数是 \(1600\) 左右的，显然我们不能接受，考虑优化方式。

首先对于状态 \(u, v\) 它可能是不存在的，因为 \(u, v\) 在 Trie 树上的形态必然是祖先和子代的关系，状态数来到 \(320\) 左右，再考虑 \((u, v)\) 和 \((v, u)\) 在上述图中是对称的存在，考虑在矩阵中所成一个状态即可。

\(\color{blueviolet}{CF1511G}\)

此题是神仙题。

首先转化问题，对于一个询问只要判断 \(\bigoplus \limits _{l \le c_i \le r} c_i - l\) 是否等于 \(0\) 即可。

设 \(f_{i, j}\) 表示 \(\bigoplus \limits _{i \le c_i \le i + 2 ^ j - 1} c_i - i\)，考虑如何倍增转移。

\(f_{i, j}\) 由 \(f_{i, j - 1}\) 与 \(f_{i + 2 ^ {j - 1} - 1, j - 1}\) 两部分组成，前者的异或和可以直接转移过来，后者包括的元素每个会与需要的值相差 \(2 ^ {j - 1}\)，所以需要额外异或上后者元素个数个 \(2 ^ {j - 1}\)，只需要通前缀和维护一下区间元素个数即可。

\[f_{i, j} = f_{i, j - 1} \oplus f_{i + 2 ^ {j - 1} - 1, j - 1} \oplus \left([(g_{i + 2 ^ j - 1} - g_{i + 2 ^ {j - 1} - 1}) \mod 2 = 1] \times 2 ^ {j - 1} \right) \]

求答案也是类似的，倍增逼近即可。

\(\color{blueviolet}{CF1515G}\)

此题是好题。

首先因为要求了起点终点相同，我们只能在强连通分量中进行求解。

考虑对于一个长度为 \(len\) 的环，我们可以走一圈取得 \(len\) 的贡献，也可以走 \(t - 1\) 次取得 \(-len\) 的贡献，这是显然的。

再考虑对于两个相邻的环，我们可以同时取到两者任意多次，构造是显然的。

所以对于多个环来说，对于每一个环的贡献可以取任意次数（负数也是可行的）。

也就是说对于一个强连通分量，设其中所有环长度为 \(len_i\)，再设 \(g = \gcd(len_1, len_2, \ldots， len_cnt)\)。根据裴蜀定理只要判断 \(s = ag - bt\) 的正整数解是否存在即可，再用一次裴蜀定理可以只需判断 \(\gcd(g, t) \mid s\) 是否成立即可。

\(\color{blueviolet}{CF1469F}\)

此题是平凡题。

贪心地考虑加入一条链时，一定是让其中点连向树上的点，并且连到树上的点深度尽可能小。

更加贪心地考虑，先加入长链是更优的~~（这你还要我证明？）~~。

现在加链的策略已经固定了，考虑维护信息。

设我们连接的书上的点深度为 \(x\)，链长为 \(l\)，那么加入这条链产生以下影响：

深度为 \(x\) 的白点减少 \(1\)。
深度在 \(\left( x + 1, x +\lfloor{ \frac{l - 1}{2}\rfloor}\right]\) 内的白点增加 \(1\)。
深度在 \(\left( x + 1, x + (l - 1 -\lfloor{ \frac{l - 1}{2}\rfloor})\right]\) 内的白点增加 \(1\)。

及其显著地，用权值线段树维护，空间开大点即可。

\(\color{blueviolet}{CF1495D}\)

此题是神仙题。

考虑对于 \(x\) 和 \(y\) 共同的生成树一定包含两者的最短路径。

先假设 \(x, y\) 最短路径有且只有一条，考虑其上一点 \(z\)，\(x, y\) 两者中一者到其最短路径依然有且只有一条，为了满足 \(dis(x, z), dis(y, z)\) 不变，必须保留此最短路。

当 \(x, y\) 最短路径不止一条时，对于这两条路径上的点依然需要满足上述 \(z\) 的条件，因此多条最短路都需要保留，此时一定会成环，无法保持树的形态，也就一定无解。

现在对于 \(x, y\) 两点已有一条唯一的链链接，考虑其他点如何挂在树上。对于一个点 \(u\) 有边 \((u, v)\)，若保留此边（使得 \(v\) 为 \(u\) 的父节点）必须满足 \(dis(x, v) + 1 = dis(x, u) \land dis(y, v) + 1 = dis(y, u)\)。所以我们对于一个点找出其合法父节点个数，对所有的点乘法原理计数即可。

\(\color{blueviolet}{CF1510B}\)

此题是坏题，它让你输出方案

首先考虑转化问题，进行简单图论建模，每个状态向可以达到的状态连边，于是得到一张 DAG，设每个状态点权为其 \(1\) 的数量。

现在问题转化为对于当前 DAG 选出一些路径进行覆盖，一条路径的贡献是其终点权值加一，总贡献是所有路径贡献加和减一（最后一次不需要重置）。

首先考虑最劣情况，对于每一个点单独成为一条路径进行覆盖。每一个点可以选择一个出边把自己贡献抵消掉，这个就类似二分图最大匹配，费用流即可。

建模（设 \((u, v, w, c)\) 表示一条从 \(u\) 到 \(v\)，容量为 \(w\)，费用为 \(c\) 的边。用 \(u \to v\) 表示原图中的一条边，一个点的\(1\) 的数量设为 \(val_i\)。并设 \(id_i\) 表示 \(i\) 的入点，\(id'_i\) 表示 \(i\) 的出点。）：

对于所有的 \(i\) 连边 \((S, id_i, 1, val_i), (id'_i, T, 1, 1)\)。（到源点费用为 \(1\) 是因为要加上重置一次。）
对于 \(u \to v\)，建边 \((id_u, id'_v, 1, -val_u)\)。

\(\color{blueviolet}{CF1523E}\)

此题是好题。

从期望定义入手进行推导。

\(\begin{aligned} E(x) & = \sum \limits_{i = 1}^n P(x = i) \times i\\ & = \sum \limits_{i = 1}^n P(x = i) \times \sum \limits_{j = 0}^{i - 1} 1 \\ & = \sum \limits_{i = 1}^n \sum \limits_{1 \le j \le i} P(x = i) \\ & = \sum \limits_{j = 1}^n\sum \limits_{j \le i} P(x = i) \\ & = \sum \limits_{j = 1}^n P(x \ge j)\end{aligned}\)

现在考虑求 \(P(x \ge j)\)，意义上理解这是在操作进行到第 \(j\) 轮时还没停止的概率，也可以理解为已经点亮 \(j - 1\) 盏灯后依然未停止的概率。

先钦定 \(j - 1\) 盏灯是点亮的，再向其中 \(j - 2\) 个空位中每个放入 \(k - 1\) 个暗灯。放完暗灯还有 \(n - (k - 1) \times (j - 2)\) 个位置，在其中选择 \(j - 1\) 个亮灯可以得到合法方案数，再除以总方案数即可。

\[P(x \ge j) = \frac{\dbinom{n - (k - 1) \times (j - 2)}{j - 1}}{\dbinom{n}{j - 1}} \]

对其求和即可。

\(\color{blueviolet}{CF1530F}\)

此题是神秘题。

考虑反着做，将至少有一行或一列或一条对角线全为 \(1\) 概率转换为所有行列对角线都至少有一个 \(0\)。

先不考虑行与对角线，只考虑满足所有列都至少有一个 \(0\) 该怎么做，为了使得我们的不完全做法有扩展性，我们考虑使用容斥。

过程如下：

加上至少有 \(0\) 列全为 \(1\) 的概率。（对于至少有 \(x\) 列全为 \(1\) 的概率，可以理解为我们选定 \(x\) 列，使得其全为 \(1\)（概率相乘），其他列的 \(0/1\) 情况我们不考虑（概率为 \(1\)）。而选定的 \(x\) 列的所有情况概率要加和，比如我选定 \(1\) 列，那么情况总数有 \(n\) 种，这些情况的概率都要加和。）
减去至少有 \(2\) 列全为 \(1\) 的概率。
加上至少有 \(3\) 列全为 \(1\) 的概率。
以此类推。

这样容斥并不难理解，我们需要求的是所有列至少有一个 \(0\) 的情况，对于第一步加的概率显然是全情况的概率，我们减去其中有一列为 \(1\) 的概率，但此时对于两行为 \(1\) 的情况我们减了两遍。举个例子，对于 \(1,2\) 号列全为 \(1\) 的某种情况，我们选定 \(1\) 号列时和选定 \(2\) 好列时分别减去了一遍，所以要在接下来的运算中将其加回来，以此类推。

接下来考虑在这样计算列的贡献时计算行的贡献，首先每一行的贡献互不影响，考虑固定选定的列进行某一行的运算，我只要保证舍去行的全为 \(1\) 的概率即可。我们设 \(f_{i,j}\) 表示对于第 \(i\) 行，选定 \(j\) 状态列（\(j\) 是一个状压状态，这里选定其中的列就相当于在第 \(i\) 行中该位置一定为 \(1\)。），不考虑其他位置 \(0/1\) 状态的概率。这个东西显然是可以预处理的。

于是就有第 \(i\) 行在状态 \(j\) 下的贡献概率 \(g_{i, j} - g_{i, 2 ^ {n - 1}}\)，其中我们减掉的是此行全为 \(1\) 的状态，也就是上文说到舍去的部分

最后对角线与列的处理相同，枚举一下状态即可，使得一行与对角线交点的位置为 \(1\) 即可。