做题笔记 2023.3

准备倒序的把这个月做过的有意思的题都写一写简要题解，当然也可能有些稍微古早一些的题目。

ABC213G Connectivity 2 展开目录

题目让我们对 $1$ 与 $k$ 连通的生成子图计数，这个东西是不好做的，结合数据范围，考虑转化为求集合 $S$ 内点连通，剩余点任意连边的方案数，进一步，我们要求的即为：

• $f(S)$，表示 $S$ 内任意连边的方案数。
• $g(S)$，表示 $S$ 内点连通的方案数。

最后的答案可以表示为：
$$\sum _{\{1,k\}\subseteq S}g(S)f(V\setminus S)$$
前者是好做的，我们可以先求出两个端点都在 $S$ 中的边数 $cnt$，则 $f(S)=2^{cnt}$。

本题最 educational 的地方在于 $g(S)$ 的计算。直接计算连通是困难的，考虑容斥转化为计算不连通的方案数，我们最后使用的 $g(S)$ 都满足 $1\in S$，若 $S$ 不连通，则 $1$ 所处的连通块是 $S$ 的真子集，剩余部分可以任意连边（形成一个或多个连通块），于是我们有：
$$g(S)=f(S)-\sum _{1\in T⊊S}g(T)f(S\setminus T)$$
这种转移方式在很多连通性相关的题目中都能见到。

计算答案即可，第二部分使用子集枚举的复杂度为 $O((m+n)2^n+3^n)$，使用子集卷积可以做到 $O((m+n^2)2^n)$。

CF1685D1 Permutation Weight (Easy Version) 展开目录

$\sum |q_i-P_{q_{(imodn)+1}}|$ 是个很难看的东西，首先考虑将编号对齐，设 $pr{e}_i$ 表示 $q$ 中 $i$ 前面的那个数，形式化的，$pr{e}_{q_{(imodn)+1}}=q_i$，这样，原式化为 $\sum |pr{e}_i-P_i|$。

不难发现 $pre$ 是一个置换环个数为 $1$ 的排列（在原序列上后一个数指向前一个数），于是一个直观的想法是我们通过若干次 swap 使得 $P$ 的环数变为 $1$，为了最小化代价，考虑遍历 $1\sim n-1$，若 $i$ 与 $i+1$ 不在一个环内，则交换 $i$ 和 $i+1$，这样两个环被合并，单次操作代价为 $2$，总代价为 $2(c-1)$，其中 $c$ 为 $P$ 置换环的个数。

考虑证明 $2(c-1)$ 是代价的下界。这部分证明很玄妙。

建图，$P_i$ 向 $pr{e}_i$ 连边，图中会形成若干个环，单个环的最小代价为 $2(siz-1)$，取到最小代价当且仅当从环上的最小点开始走一圈得到的序列先上升再下降，并且把所有点的编号拉出来排序后是连续的。于是我们希望最大化环的个数。

重新建图，为 $P$ 的置换环编号，令 $be{l}_i$ 表示 $i$ 所处置换环的编号，由定义有 $be{l}_i=be{l}_{P_i}$，我们让 $be{l}_{P_i}$ 向 $be{l}_{pr{e}_i}$ 连边，注意可能产生自环或重边。这样连边等价于 $be{l}_i\to be{l}_{pr{e}_i}$，也就相当于沿着 $be{l}_{q_i}$ 走了一圈，显然这样可以走到所有置换环，所以这张新图应当是连通的。

在原图中从每个环中删去一条边不会影响原图和新图的连通性，而新图中至多能删去 $n-c+1$ 条边（新图点数为 $c$，连通至少需要 $c-1$ 条边），所以环个数的上界是 $n-c+1$，于是代价的下界为 $2(n-(n-c+1))$ 即 $2(c-1)$。

AGC019F Yes or No 展开目录

很有意思的一道题。考虑如果 $n\ne m$，则我们一定猜数量比较多的那种答案，如果 $n=m$，则猜啥都一样。

将原问题放在网格图上考虑则相当于，我们从 $(n,m)$ 开始随机游走，如果 $n\ne m$，不妨设 $n>m$，我们的决策是固定的，并且最终总会走到某个 $(i,i)$，在这个过程中我们一共猜对了 $n-i$ 道题，如果 $n=m$，我们期望答对 $\frac{1}{2}$ 道题后再次回到 $n\ne m$ 的情况。

不难发现 $n\ne m$ 的情况中我们一共会答对 $max(n,m)$ 道题，剩下的部分我们只需要统计我们期望会经过多少次 $y=x$。这等价于对于每个 $(i,i)$，统计有多少条路径经过它。

最终答案为：
$$max(n,m)+\sum _{i=1}^{min(n,m)}(\genfrac{}{}{0ex}{}{n+m-2i}{n-i})(\genfrac{}{}{0ex}{}{2i}{i})$$
线性计算即可。

CF1781G Diverse Coloring 展开目录

受题解启发，晚上想到一种奇怪的构造方法。

首先断言答案只能为 0 1 2，并且答案为 2 当且仅当样例中的那种情况，即一个三度点，三个一度点。接下来考虑构造。

基本思想仍然是将树划分成大小为 2 和 3 连通块，但这样可能会出现根节点无法分配的情况。

如果我们能够在树上找到一个二度点，并且满足与其相邻的点中至少有一个是叶子，我们让这个点为根，由于一个儿子一定会传上来 1，根节点一定能够分配到某个连通块内。

但问题是这样的点可能不存在。当这样的点不存在时，考虑找到一个三度点满足与其相邻的点中至少有两个是叶子，我们去掉一个叶子就得到了理想的二度点。于是在删掉叶子后跑之前的构造算法，再考虑将叶子加回来。如果我们构造了奇数个三连通块，新增的这个叶子可能导致染色方案不平衡，但我们可以调整一个三连通块的染色方案，注意这个三连通块不能包含根节点。有没有可能仅存在一个三连通块并且该三连通块包含根节点？答案是有且仅有样例当中答案为 2 的那种情况，否则，除了唯一的三连通块其余点能被划分为二连通块，我们必然能够在原树中直接找到一个上面提到的理想二度点，这就产生了矛盾。

上述算法无法处理仅有两个点的情况，在代码实现时注意一些细节即可。

CF938G Shortest Path Queries 展开目录

路径边权异或和有非常好的性质，因为一个数异或两次之后就会变成 0，所以求路径边权异或和可以直接把两端点到根路径的异或和异或起来。更近一步的，在本题中，我们可以在图中走出任意路径，一条边可以经过多次，不难发现这等价于我们任取一条简单路径，然后异或上图中的若干个环，由于保证查询时图连通，所以我们不关心环是否可达。我们也不关心环嵌套的情况，两个小环的异或就是大环，其他情况同理。

如果没有修改，我们可以先求出图的任意生成树，对于所有非树边，计算其与树边构成的环的异或和并加入线性基，每次查询先取出两点在树上的简单路径，然后用线性基求异或最小值即可。

如果带修，容易发现加边容易删边困难，所以考虑线段树分治。这里考虑我们如何维护每个点到跟路径的边权异或和，实际上在并查集的边上加上边权即可。

CF1034E Little C Loves 3 III 展开目录

本题要求模 4 意义下的子集卷积，传统 $O(n^2{2}^n)$ 子集卷积的思想是，通过加上一维表示集合大小，我们可以将 $i\mathrm{or}j=k\wedge i\mathrm{and}j=0$ 转化为 $i\mathrm{or}j=k\wedge count(i)+count(j)=count(k)$。

更进一步的，如果 $i\mathrm{or}j=k$，$count(i)+count(j)\ge count(k)$，我们的思路是通过某种方式，让 $count(i)+count(j)>count(k)$ 的 $(i,j)$ 最终对 $k$ 贡献为 $4$ 的倍数，这样其在模意义下就不会被计算。

这样做法也就呼之欲出了，令 $a_i\leftarrow a_i\times 4^{count(i)}$，$b$ 同理，FMT / FWT 求出 $c$ 后，令 $c_i\leftarrow c_i/4^{count(i)}$ 即为最终答案。

CF794G Replace All 展开目录

如果两个串完全相同， $A,B$ 均可任选，答案为 $(\sum _{i=1}^n{2}^n{)}^2$。

否则，设 $x$ 比 $y$ 多 $p$ 个 $A$，$y$ 比 $x$ 多 $q$ 个 $B$，不难发现 $p,q$ 必然同号（或都为 $0$），否则无解，下面如果 $p,q$ 均为负，我们对两个数取相反数。

先证一个 lemma，$A,B$ 有公共循环节，长度为 $gcd(|A|,|B|)$。考虑若两个串开头字符相同，我们可以一起把他们消掉，这样总能找到一个时刻两串开头不同，由于两串在替换过后相同，我们知道短串必然是长串的前缀，那么考虑将长串替换为短串 + 后缀，这个过程类似更相减损法，最终我们会得到长度为 $gcd$ 的公共循环节。

若 $p=q=0$，$A,B$ 长度任意，答案为 $\sum _{i=1}^n\sum _{j=1}^n{2}^{gcd(i,j)}(\ast )$。

推式子。
$$\begin{array}{rl}(\ast )=& \sum _{k=1}^n{2}^k\sum _{i=1}^n\sum _{j=1}^n[gcd(i,j)=k]\\ =& \sum _{k=1}^n{2}^k\sum _{i=1}^{\lfloor \frac{n}{k}\rfloor }\sum _{j=1}^{\lfloor \frac{n}{k}\rfloor }[gcd(i,j)=1]\end{array}$$
这里有两条路可以走，一种是用欧拉函数。
$$(\ast )=\sum _{k=1}^n{2}^k\cdot 2(\sum _{i=1}^{\lfloor \frac{n}{k}\rfloor }\phi (i)-1)$$
做一个欧拉函数前缀和即可，复杂度线性。

另一种是莫反。
$$\begin{array}{rl}(\ast )=& \sum _{k=1}^n{2}^k\sum _{i=1}^{\lfloor \frac{n}{k}\rfloor }\sum _{j=1}^{\lfloor \frac{n}{k}\rfloor }\sum _{d\mid gcd(i,j)}\mu (d)\\ =& \sum _{k=1}^n{2}^k\sum _{d=1}^{\lfloor \frac{n}{k}\rfloor }\mu (d){\lfloor \frac{n}{dk}\rfloor }^2\end{array}$$
对内层整除分块，复杂度是一堆根号加起来，考虑积分。
$$\begin{array}{c}f(x)=\sqrt{\frac{n}{x}}\\ \begin{array}{rl}{\int }_1^{n}f(x)\mathrm{d}x& ={\int }_1^n{n}^{\frac{1}{2}}{x}^{-\frac{1}{2}}\mathrm{d}x\\ & =n^{\frac{1}{2}}\cdot n^{\frac{1}{2}}\\ & =n\end{array}\end{array}$$
故总复杂度线性。

若 $p\ne q$，则 $A,B$ 长度比值确定，先同除 $gcd$ 使 $p,q$ 互质，则答案为 $\sum _{i=1}^{\lfloor \frac{n}{max(p,q)}\rfloor }{2}^i$，预处理即可。

计数则考虑枚举 $p,q$，还需要推一个组合数的式子，总之是一个 Vandermonde 卷积的形式。记得把两串完全相同的情况特殊处理。

CF526D Om Nom and Necklace 展开目录

一种鬼畜做法。KMP 可以求最小循环节，但是反正我不是这么做的。

首先我们要求的东西可以表示为 $A^{k}B$ 的形式，$B$ 是 $A$ 的前缀。

hash 可以判断一个串能否表示成 $A^k$ 的形式，把开头长度为 ${\displaystyle \frac{len}{k}}$ 的串 concatenate $k$ 次即可，这个过程可以快速幂实现。如果我们已经确定了 $A^k$，接下来只需要找一个 lcp 即可，这部分可以二分 + hash 实现，复杂度 $O(n\log n)$。

但我们想要做到线性。一种思路是，我们贪心的选取最长的 $A^k$，实现时考虑将序列遍历一遍，每次检查当前前缀能否作为 $A^k$，如果能则将 $B$ 置为空串，否则检查当前字符能否接在 $B$ 的末尾。

考虑正确性，首先这个贪心只可能将有解判成无解。如果出现了这种情况，则意味着我们有一个较短的 $A^{\prime }$ 使得当前前缀可以表示为 $A^{\prime k}{B}^{\prime }$ 的形式，而较长的 $A$ 则不行。此时，除 $k=1$ 的情况外，我们可以证明 $A^{\prime }$ 和 $A$ 有长度为 $gcd(|A|,|A^{\prime }|)$ 的公共循环节，类似 Replace All，注意整个证明过程需要的串长是 $|A|+|A^{\prime }|$，所以我们要求 $k>1$。有了循环节之后则不难发现，$B^{\prime }$ 形如若干循环节加上一个前缀，那么 $B$ 理应是 $A$ 的前缀，这就产生了矛盾，另外 $k=1$ 的情况是 trivial 的，于是正确性就有了保证。

总复杂度 $O(n+{\displaystyle \frac{n}{k}}\log k)$。

ARC016D 軍艦ゲーム展开目录

很有趣的题目。本来是个简单的期望 dp，转移方程只涉及一个未知量 $f_{1,h}$，不妨将其设为 $x$，则所有 dp 值可以表示为关于 $x$ 的一次函数，dp 完之后解方程即可。但是你发现转移方程中出现了取 $min$ 操作，这就不好办了。

考虑二分 $x$，设对于某个 $x$ 值算出来的 $f_{1,h}$ 为 $g(x)$，可以证明 $g^{\prime }(x)\le 1$，具体的，考虑按反向拓扑序归纳，边界情况的 dp 值不变，如果转移到 $f_{1,h}$ 则 $\mathrm{d}f=\mathrm{d}x$，于是上面的结论是显然的。所以 $g(x)-x$ 单调不增，并且零点唯一，至于为啥唯一好像也没啥证明，感性理解一下。

然后就做完了，注意 $1$ 是不能自己转移到自己的。

CF1798C Candy Store 展开目录

赛时降智，也可能是手上没有草稿纸的缘故。这场应该算是非常简单了。当然反正我是 div 1 选手，又不会掉分。

我第一眼就是 ${10}^9$ 级别的数约数个数最多就是 ${10}^3$ 级别，所以暴力 dp 就能过，问题在于不能快速求出所有约数。然后就被这个 dp 思路带跑了。

实际上不难发现这个题直接贪心是没有问题的，考虑如何快速检验一段合不合法。

价格肯定是越小越好，最小是 $\mathrm{lcm}(b_i)$，我们要求 $a_i$ 是 $\mathrm{lcm}/b_i$ 的倍数，考虑同乘 $b_i$，转化为要求很多个数是同一个数的倍数，综上，我们只需要 $gcd(a_i\cdot b_i)$ 是 $\mathrm{lcm}(b_i)$ 的倍数即可。

本作品采用 知识共享署名 - 非商业性使用 - 相同方式共享 4.0 国际许可协议 进行许可。