task3

[TOC]

1. USACO23FEB P - Watching Cowflix P [Keter] ✔️

题面

给定一棵 $n$ 个点的树，有些点是关键点，你需要选择若干个连通块，使得这些连通块覆盖所有关键点，对于一种方案，你需要付出的代价是 $\text{连通块的并包含的点数}+k\times\text{连通块个数}$

对 $k=1,2,\cdots,n$ ，求最小代价

$1\le n\le2\times10^5$

题解

做法 1

Sol

两个点 $u,v$ ，设其之间最短路点数（不含 $u,v$ ）为 $d$ ，那么两个点分在两个连通块内产生的贡献为 $2k+2$ ，属于同一个连通块产生的贡献为 $k+d+2$ ，因此如果 $k\ge d$ ，那么我们把这两个点划在一个连通块一定不劣

因此，枚举 $k$ 时，当前还没被合并的关键点一定两两距离 $>k$ ，而这样的点最多只有 $O(\frac nk)$ 个，那么我们可以通过在虚树上的一个 $O(\frac nk)$ 的树形 dp 计算答案

实现时，注意到 $k-1$ 时被合并到一起的连通块，在 $k$ 的最优解中一定还合并在一起，因此我们每次可以直接根据 dp 值判断有哪些点被合并到了一起，然后将它们缩起来，这样就自动保证了点数是 $O(\frac nk)$ 级别的

总复杂度 $O(n\ln n)$

做法 2

Sol

考虑有一种弱智的策略是将整棵树选成一个连通块，代价是 $n+k$

也就是说，最优解的最小连通块个数要 $\le\frac nk+1$ ，而这个东西随 $k$ 变化只有 $O(\sqrt n)$ 个连续段，这个东西又满足单调性，因此我们考虑类似于在线段树上二分找出来所有 $O(\sqrt n)$ 个端点，这需要求 $O(\sqrt n\log n)$ 个 $k$ 值的最小连通块个数，因此总复杂度是 $O(n\sqrt n\log n)$ ，但官方题解说这是 $O(n\sqrt n)$ ，不知道是不是有什么高论

求出来每个位置的最小连通块个数之后就比较简单了，直接代入一次函数算一下即可

2. UOJ771 - 科考工作 [Keter]

题面

给定 $2n-1$ 个数，选出其中的 $n$ 个使得和为 $n$ 的倍数，给出构造或者判定无解

$2\le n\le3\times10^5$ ，保证 $n$ 是质数

题解

Sol

有结论：对于质数 $n$ ，任意 $n-1$ 个非零数 $d_1,d_2,\cdots,d_{n-1}$ ，它们的子集和一定能凑出 $0,1,\cdots,n-1$ 中的所有余数

证明：设前 $i$ 个数的凑出的子集和的集合是 $S_i$ ，我们试图证明 $|S_{i+1}|=n$ 或 $|S_{i+1}|\ge|S_i|+1$

如果 $|S_{i+1}|=|S_i|$ ，也即 $S_{i+1}=S_i$ ，那么 $S_i$ 中的每个数 $+d_i$ 仍然在 $S_i$ 内，也就是对于 $x\in S_i$ ，任意 $k$ 都满足 $x+dk$ 在 $S_i$ 中，因此 $S_i$ 必须为全集

有了这个结论，如果原题中众数出现次数 $\ge n$ ，那么直接选全相等的即可，否则一定可以将 $2n-1$ 个数分成 $n-1$ 对数和一个单独数，满足其中每对数内部不相等，我们假设全选第一个数，就转化成了上面的问题

考虑如何构造方案，我们用一个布尔数组维护 $S$ 集合，那么我们只要保证每加一个 $d_i$ 能够使 $S$ 的大小增加 $1$ 即可，也就是找到任何一个 $x\in S$ 且 $x+d_i\notin S$ ，我们将所有数按其 $\times d_i^{-1}$ 的值排成一个环，我们的目标是让某一个 $y$ 在 $S$ 中，如果已经有 $y\in S$ 那么直接输出方案即可，否则 $y\notin S$ ，但是 $0$ 在 $S$ 中，也就是说 $0\sim y\times d_i^{-1}$ 这些数中一定有一个 $z$ 满足 $z\times d_i\in S$ 但 $(z+1)\times d_i\notin S$ ，因此直接二分找到一个位置即可

复杂度 $O(n\log n)$

3. ARC139B - Make N [Euclid]

题面

你有一个整数 $P=0$ ，你可以进行：

花费 $X$ 的代价，使 $P\leftarrow P+1$
花费 $Y$ 的代价，使 $P\leftarrow P+A$
花费 $Z$ 的代价，使 $P\leftarrow P+B$

求让 $P=N$ 的最小代价

$1\le N,A,B,X,Y,Z\le10^9$

题解

Sol

如果只有两种操作，那么是非常好做的：直接 exgcd 求一下通解，代价就是一个一次函数，求一下区间极值即可

考虑怎么把三种操作变成两种操作，首先如果 $AX\le Y$ ，那么我们肯定不会用第二种操作

否则，第一种操作的数量一定不会超过 $A$

那么如果 $A\le\sqrt N$ ，我们可以直接枚举第一种操作的次数，复杂度 $O(\sqrt N\log N)$

如果 $A>\sqrt N$ ，那么第二种操作的次数一定不超过 $\frac NA$ 也即 $\sqrt N$ ，那么枚举第二次操作的次数，复杂度 $O(\sqrt N\log N)$

总复杂度 $O(\sqrt N\log N)$

4. ARC139D - Priority Queue 2 [Keter] ⭐

题面

有序列 $a_1,a_2,\cdots,a_n$ ，值域为 $[1,m]$ ，给定 $k,x$ ，你需要进行 $k$ 次如下操作：

向 $a$ 中插入一个数 $b_i$ ，满足 $b_i\in[1,m]$ ，然后删除 $a$ 中第 $x$ 小数

对于所有 $m^k$ 种可能的 $b_i$ ，求操作后 $a$ 中元素之和的和，对 $998244353$

$1\le n,m,k\le2000$

题解

Sol

神秘。

我们把元素求和转为求 $\ge i$ 的元素个数之和。

如果两个数相等，我们认为时间戳更小的数更靠前，将所有 $a_i$ 和 $b_i$ 拿出来排成一个 $n+m$ 的序列 $c$ ，那么最后的 $a$ 序列就是将 $c[x:x+k-1]$ 挖掉后得到的序列

设 $a$ 中出现了 $cnt_i$ 次 $i$ ，我们枚举这 $cnt_i$ 个 $i$ 最后对应着 $c$ 中的哪个区间，由于时间戳更小的数更靠前，所以这个区间前的数都 $<i$ ，区间后的数都 $\ge i$ ，那么就可以得到 $\ge i$ 的数的个数，而方案数是可以用组合数快速计算的

复杂度 $O((n+k)m\log(n+k))$

5. USACO23OPEN P - Pareidolia P [Keter]

题面

定义一个字符串的权值是最大的 $t$ 使得 $\texttt{bessie}^t$ 是该字符串的子序列

给定一个字符串 $s$ ， $m$ 次修改，每次修改一个字符的值，修改完之后查询 $s$ 的所有子串的权值和

$1\le |s|,m\le2\times10^5$

题解

Sol

求的东西可以直接用线段树维护，重点在于如何维护，别人的维护方式我没看懂，这里介绍一下比较麻烦的维护方式：

我们在合并到区间 $[L,R]$ 时，需要加上越过 $mid$ 的贡献，首先我们可以贪心匹配子序列，那么我们就需要知道：

$[L,mid]$ 匹配到第 $i$ 个字符的后缀的个数 - num[i]
$[L,mid]$ 匹配到第 $i$ 个字符的后缀总共匹配出多少个 bessie - len[i]
一个匹配到第 $i$ 个字符的字符串进入 $[mid+1,R]$ 的每个前缀匹配，新产生的 bessie 数量之和 - in[i]

而为了维护这些信息，我们还需要知道：

匹配到第 $i$ 个字符的字符串经过一个区间 $[L,R]$ 之后会匹配到第几个字符 - to[i]
匹配到第 $i$ 个字符的字符串经过一个区间 $[L,R]$ 之后会新匹配出多少 bessie - tlen[i]

然后对着这些信息搓一下转移就行了。

复杂度 $O(6n\log n)$

6. USACO23OPEN P - Good Bitstrings P [Euclid]

题面

string gen_string(int64_t a, int64_t b) {
	string res;
	int ia = 0, ib = 0;
	while (ia + ib < a + b) {
		if ((__int128)ia * b <= (__int128)ib * a) {
			res += '0';
			ia++;
		} else {
			res += '1';
			ib++;
		}
	}
	return res;
}

$t$ 组数据，每次给定两个数 $A,B$ ，求有多少 gen_string(A,B) 的前缀 $s$ 使得存在 $x,y$ 满足 gen_string(x,y)=s

$1\le t\le10,1\le A,B\le10^{18}$

题解

Sol

答案等于以下两个部分的数量之和（ $1\le x\le A,1\le y\le B$ ）：

满足 $\frac xy>\frac AB$ 且 $\frac xy$ 比所有分母小于 $y$ 的 $>\frac AB$ 的分数距离 $\frac AB$ 更近
满足 $\frac xy\le\frac AB$ 且 $\frac xy$ 比所有分母小于 $y$ 的 $\le\frac AB$ 的分数距离 $\frac AB$ 更近或相等

这个很像 Stern-Brocot Tree，于是我们开始在这棵树上找性质

我们发现第一部分就是在查找 $\frac AB$ 的时候经过的向左走的点的个数

而第二部分稍微麻烦一些，因为要考虑分子分母不互质的情况，如果向右走的点依次排列为 $\frac{a_1}{b_1},\frac{a_2}{b_2},\cdots,\frac{a_k}{b_k}$ ，那么我们的答案就是 $\sum\limits_{i=1}^{k-1}\left\lfloor\dfrac{b_{i+1}}{b_i}\right\rfloor+\left\lfloor\dfrac B{d_k}\right\rfloor$ ，而出于一些原因，同一个向右走的连续段内的 $\left\lfloor\dfrac{b_{i+1}}{b_i}\right\rfloor$ 都为 1，也就是说相比第一部分只需要加上连续段之间的贡献即可

而由于 Stern-Brocot Tree 的神秘性质，查找一个分数的向左走/向右走的连续段是 $O(\log n)$ 级别的

那么我们二分找连续段，剩下的东西就都是可以 $O(1)$ 统计的，总复杂度 $O(\log^2B)$

7. USACO23OPEN P - Triples of Cows [Keter] ⭐

题面

给定一棵 $n$ 个点的树，依次从这棵树里面删点，第 $i$ 次操作删第 $i$ 个点，删完一个点后将与 $i$ 直接相连的点之间两两连上边

每次操作前，求满足 $a$ 与 $b$ 有连边， $b$ 与 $c$ 有连边且 $a\neq b,b\neq c,c\neq a$ 的有序三元组 $(a,b,c)$ 的个数

$1\le n\le2\times10^5$

题解

Sol

答案就是 $\sum\text{deg}(\text{deg}-1)$ ，我们只要对 $0\le t\le2$ 维护 $\sum\text{deg}^t$ 即可

考虑这个删除加边操作的性质，我们不妨把删除的点打上标记，不真的删点加边， $\deg_u$ 其实就是从当前点 $u$ 出发，除了起点和终点，其他路径上的点都必须是打上标记的点，能到达多少未被标记的点，因此我们可以考虑对于一个删除的点的连通块来考虑

我们充分发扬树的性质，树上的点有多个儿子，但只有一个父亲，我们考虑利用这一点

我们可以在一个删除的连通块内，维护所有向下邻接的未被删除的连通块的 $\sum\deg^t$

每次删除一个点时，我们将儿子合并上来，这会涉及一个 $\deg\rightarrow\deg+x$ 的过程，而这是好维护的

但我们还需要更新祖先的上一个未被删除的点的 $\deg$ ，这会涉及到单点查 $\deg$ ，于是我们可以再维护一个 $\text{vdeg}$ ，表示只考虑子树中的点的 $\deg$ ，而这个每次需要更新的点都是 $O(1)$ 的

总复杂度 $O(n\alpha(n))$

8. AGC028F - Reachable Cells [Keter] ⭐

题面

给定一个 $n\times n$ 的字符矩阵，由 1~9 和 # 组成

定义一个方格对 $(X,Y)$ 是合法的当且仅当：

$X,Y$ 不同
$X,Y$ 都不为 #
存在一条不经过 # 的只向右或向下的路径从 $X$ 到 $Y$

定义方格对的权值是两个格子上的数的乘积，求所有合法方格对的权值和

$1\le n\le500$

题解

Sol

手模一下，发现每一行从某一个起点能到达的好像都是一个区间，里面有一些不管怎么样也不能到达的

那么这启发我们怎么样把能到达的变成一个区间。

首先，我们可以 dp 求出 $L_{i,j,k},R_{i,j,k}$ ，分别表示从 $(i,j)$ 出发能到达第 $k$ 行的最左边/最右边的格子

我们声称，只要我们将当前能到它的点都计算过的点全部变成障碍，那么我们到达每一行的格子都是一个区间

这是好证的，因为如果此时 $(i,j)$ 之前依然有能到达某 $(k,x)$ 的点，那么这个路径一定跟 $(i,j)\rightarrow (k,L_{i,j,k})$ 或 $(i,j)\rightarrow(k,R_{i,j,k})$ 相交，所以 $(i,j)$ 就与 $(k,x)$ 可达

那么我们需要将所有考虑完的点变成障碍，我们有如下方式：时刻将满足 $(x-1,y)$ 和 $(x,y-1)$ 都是障碍的点变为障碍，这个可以用 dfs 实现

证明也比较简单，如果有某个点 $(x,y)$ 没被删掉，那么从它一定有一个路径能够走到 $(i,j)$ 之前，从而矛盾

因此我们只要维护出每行的权值的前缀和即可，而我们会有 $O(n^2)$ 次把一个点修改成障碍的操作，每次 $O(n)$ 更新前缀和即可

因此复杂度 $O(n^3)$

9. ARC159F - Good Division [Keter] ✔️

题面

给定一个长为 $2n$ 的序列 $a_1,a_2,\cdots,a_{2n+1}$ ，你需要将这个序列分成若干连续子段，使得每个连续子段可以通过如下方式删空：

选择一个 $a_i\neq a_{i+1}$ ，将 $a_i$ 和 $a_{i+1}$ 删去

求划分方案数，对 $998244353$ 取模

$1\le n\le5\times10^5,1\le a_i\le2n$

题解

Sol

一个子段不合法当且仅当其长度为奇数，或者其众数出现次数 $\ge\frac{len}2$ ，称其为绝对众数

有一个显然的 dp， $dp_i=\sum dp_j[[j+1,i]\text{合法}]$

固定一个位置 $i$ ，那么以 $i$ 结尾的所有区间最多 $O(\log n)$ 种绝对众数，以 $i$ 为开头的区间也最多 $O(\log n)$ 种绝对众数，因此我们可以考虑从长度为偶数的所有 dp 值中把不合法的区间减去

做法 1

对于一个 $x$ ，其在 $[j+1,i]$ 中为绝对众数当且仅当 $cnt_{x,i}-cnt_{x,j}>\frac{i-j}{2}$ ，即 $2cnt_{x,i}-i>2cnt_{x,j}-j$

由上面的结论，一个下标只在 $O(\log n)$ 个 $x$ 中作为 $i$ ，只在 $O(\log n)$ 个 $x$ 中作为 $j$ ，因此我们可以对每个 $x$ 开一个数据结构，这个数据结构需要支持插入一个数，查询小于某数的权值和，可以用平衡树或树状数组实现

复杂度 $O(n\log^2n)$

做法 2

还是那个 dp，直接转移不太好做，所以我们考虑分治

当前在区间 $[l,r]$ ，我们要求 $[l,mid]$ 对 $(mid,r]$ 产生的贡献，那么就要统计所有跨过 $mid$ 的有绝对众数的区间，那么这样的区间在 $[l,mid]$ 的部分内有绝对众数或在 $(mid,r]$ 的部分内有绝对众数，因此需要考虑的绝对众数只有 $O(\log n)$ 种

对于一种绝对众数 $x$ ，我们可以顺着扫一遍区间，将所有等于 $x$ 的位置视为 $1$ ，其余的视为 $-1$ ，由于每次查询的前缀和只会 $\pm1$ ，因此可以用桶维护，这样一次的复杂度就是 $O(r-l+1)$ ，再乘上绝对众数和分治的两个 $\log$ ，一共复杂度是 $O(n\log^2n)$

做法 3

考虑一种绝对众数 $x$ ，考虑有哪些位置可能在 $x$ 作为绝对众数的区间里

我们可以按照如下方式构造：从左到右依次加入等于 $x$ 的位置，每次加入一个数是找到左边第一个没有打上标记的 $a_i\neq x$ ，将其打上标记，对于右边第一个同理，那么最后所有打上标记的数和 $=x$ 的数就是可能在绝对众数的区间里的位置，不难发现一共有 $O(cnt_x)$ 个，用栈维护这件事情可以将复杂度也做到 $O(cnt_x)$

因此，我们只要将每个位置可能在哪些绝对众数的区间里预处理出来，调用 “做法 2” 中桶的做法就可以 $O(n)$ 完成本题

10. ARC149E - Sliding Window Sort [Safe]

题面

给定 $n,m,k$ ，表示对排列 $a_0,a_1,\cdots,a_{n-1}$ 进行了 $k$ 次排序操作，第 $i$ 次操作排序 $a[(i-1)\bmod n:(i-1)+(m-1)\bmod n]$

现在给定操作完的 $a$ ，求有多少 $a$ 的初始状态，对 $998244353$ 取模

$2\le m\le n\le3\times10^5,1\le k\le10^9$

题解

Sol

手模题。被上面的题踩爆了，来找回一点信心。

可以考虑最大值和最小值，由于这个操作的性质，最大的 $m-1$ 个数一旦被操作了，就会被带着走，那么一直操作下去，一定会有某个时刻最大 $m-1$ 个数都在排序区间的末尾，而这时其他数的位置关系就不会改变了

那么我们希望所有数都被排序过，如果没有，我们可以直接把没排序过的数扔掉，因为显然它们存不存在都没有什么关系

那么首先判一下最后一次排序后面是不是最大的 $m-1$ 个数，把无解判掉

首先，我们可以模拟一些操作，回溯 $k=n-m+1$ 的时候，那么我们就需要知道 $a[0:n-m]$ 这些数是如何形成这个相对顺序的

按下标从前向后考虑，手模一下会发现只有前缀最大值有 $m$ 种位置选择，其他的都只有 $1$ 种位置选择，再乘上最大 $m-1$ 个数内部的排序 $(m-1)!$ 即可

复杂度 $O(n)$

11. ARC145E - Adjacent XOR [Keter] ⭐

题面

给定两个长为 $n$ 的序列 $a_1,a_2,\cdots,a_n$ 和 $b_1,b_2,\cdots,b_n$

你可以进行至多 $70000$ 次如下操作：

选定一个 $k$ ，对 $2\le i\le k$ ，同时执行 $a_i\leftarrow a_i\oplus a_{i-1}$

给出一种将 $a$ 变为 $b$ 的操作序列，或报告无解

$2\le n\le1000,0\le a_i,b_i<2^{60}$

题解

Sol

首先，我们将问题转化为每次操作把 $b$ 的一段前缀改为前缀异或，将操作序列倒序就是答案

这个操作启发我们倒着依次满足 $b_n,b_{n-1},\cdots$ ，这样我们后面的操作不会影响前面的操作

这看起来像是我们要异或上一个集合，于是我们大胆猜一下有解的充要条件是对于任意 $i$ ，存在一个 $S\subseteq\{b_1,b_2,\cdots,b_{i-1}\}$ 使得 $a_i\oplus b_i\oplus S=0$ ，也就是我们可以通过操作将 $b_i$ 异或上 $\{b_1,b_2,\cdots,b_{i-1}\}$ 任意一个子集，这可以通过归纳证明

那么我们建出下标最靠前的线性基，这样对于一个基向量 $b_j$ ，进行任何操作都不会改变它是一个基向量的事实，因为 $b_j$ 只会异或上前面的数

因此我们不管怎样操作线性无关组的下标都不会变，而对于基向量 $b_j$ ，我们进行一次 $k=j+1$ 的操作即可将 $b_1\oplus b_2\oplus\cdots\oplus b_i(i>j)$ 异或上一个线性基表示中包含 $b_j$ 的数，并且不包含在 $b_j$ 之后的基，因此我们可以通过这种方式消元，那么也就只需要 $O(n\log a_i)$ 次操作

时间复杂度可以直接 $O(n^2\log a_i)$ 暴力模拟（估计 checker 也得这么写）

12. ARC153E - Deque Minimization [Keter]

题面

对于一个各位都不是 $0$ 的正整数 $x$ ，我们定义 $f(x)$ ：

初始 $y=0$ ，每次将 $x$ 的最高位放到 $y$ 的末尾或开头，定义 $f(x)$ 为能得到的最小的 $y$

给定 $y$ ，计数有多少 $x$ 满足 $f(x)=y$ ，对 $998244353$ 取模

$1\le y<10^{200000}$

题解

Sol

考虑如何求 $f(x)$ ，我们可以发现，这个定义相当于每次考虑 $x$ 的首位，如果小于等于 $y$ 的首位就将其放在开头，否则放在末尾

那么这看起来很区间 dp，我们令 $dp_{l,r}$ 表示能生成 $y_l\sim y_r$ 的 $x$ 个数：

$dp_{l,r}\leftarrow dp_{l+1,r}[y_l\le y_{l+1}]\\dp_{l,r}\leftarrow dp_{l,r-1}[y_l<y_r]$

值域只有 $9$ ，这启发我们把相同值域的合并起来，好像不是很好办，但是有两件事情：

我们从 $y$ 的开头开始找到第一个满足 $y_i>y_{i+1}$ 的位置 $id$ （如果没有则 $id=n$ ），只有 $l$ 在 $[1,id]$ 的状态是重要的
对于一种数 $v$ ，我们找到 $id$ 后面第一个 $\le v$ 的位置 $x$ ，那么对于所有 $y_l=v$ 的状态只有 $r<x$ 的状态非零

那么状态矩阵就会长成这个样子：

对于一种数，左边阶梯状显然都是 $1$ ，并且右边的转移是满的，即 $dp_{l,r}$ 可以从 $dp_{l,r-1}$ 和 $dp_{l+1,r}$ 转移过来，因此我们可以用组合数 + fft 加速这个过程

这样从下向上推，最后答案就是 $dp_{1,n}$ ，复杂度 $O(9n\log n)$

13. ARC146E - Simple Speed [Keter] ⭐

题面

给定长为 $n$ 的数列 $a_1,a_2,\cdots,a_n$ ，求有多少序列 $b$ 满足：

$b$ 中恰好有 $a_i$ 个 $i$
对于任意 $i$ ， $|b_i-b_{i-1}|=1$

对 $998244353$ 取模

$1\le n\le2\times10^5,1\le a_i\le2\times10^5$

题解

Sol

考虑对折线进行 dp， $dp_{i,j,0/1,0/1}$ 表示考虑完前 $i$ 个数，分成了 $j$ 段折线，首尾是否和起点/终点连起来

列一下转移可以发现一共只有一种：从 $dp_{i,j,o,p}$ 到 $dp_{i,a_i-j+o+p,0/1,0/1}$ ，而这是可以 $O(1)$ 做的

而且，不难归纳证明对于同一个 $i$ ，状态个数是 $O(1)$ 的，因此总复杂度 $O(n+\max a)$

14. ARC144E - GCD of Path Weights [Keter] ⭐

题面

给定一张 $n$ 个点， $m$ 条边的有向图，点有点权 $a_i$ ，保证每条边 $u\rightarrow v$ 满足 $u<v$

定义一条路径的权值为点权和，现在给出一部分点的权值，剩下的点的点权可以任意选定，求从 $1$ 到 $n$ 的所有路径权值的 $\gcd$ 最大为多少，如果没有最大值输出 -1

$2\le n\le3\times10^5,1\le m\le3\times10^5,1\le a_i\le10^{12}$

题解

Sol

有结论：对于一个 DAG，边有边权，从 $1$ 到 $n$ 的所有路径都是 $x$ 的倍数，当且仅当我们去除掉所有 $1$ 不能到和不能到 $n$ 的点后，可以给每个点分配一个势能 $p_i$ ，使得对于任意一条边 $(u\rightarrow v,w)$ ， $p_v\equiv p_u+w\pmod x$ ，并且 $p_1\equiv p_n\pmod x$

这个证明应该不难。

那么我们将原题的点权转化为边权，只要对每个由确定的边形成的连通块判断一下就能判断 $1$ 到 $n$ 的所有路径 $\gcd$ 是否可能为 $x$

但是我们要找最大的 $x$ ，我们发现用这个结论判断的过程中，实际上判断一个点的不同权值是否模 $x$ 同余，那我们直接对这些权值做差再取 $\gcd$ 就能找到满足条件的 $x$

总复杂度 $O(m\log a_i)$

15. ARC141D - Non-divisble Set [Euclid] ⭐

题面

给定长为 $n$ ，值域为 $[1,2m]$ 的数列 $a_1,a_2,\cdots,a_n$ ，保证 $a_i$ 互不相同

定义一个集合 $S\subseteq\{a_1,a_2,\cdots,a_n\}$ 是好的，当且仅当 $|S|=m$ 且 $S$ 中任意两个数没有整除关系

对于 $i\in[1,n]$ ，求 $a_i$ 是否能出现在一个好的集合中

$1\le m\le3\times10^5,m\le n\le2m$

题解

Sol

这个 $2m$ 和 $m$ 看起来很抽屉原理，所以我们想怎么构造 $m$ 个抽屉

经过一些常识，我们发现可以构造形如 $\{t\times2^0,t\times2^1,\cdots,t\times2^k\}$ 的抽屉，其中 $t=1,3,\cdots,2m-1$ ，这样每个抽屉都要恰好选一个

但是这只解决了 2 倍的关系，我们还需要考虑其他倍数关系，我们设第 $i$ 个集合中选出的数是 $t_i$ ，那么相当于要求 $v_2(t_k)>v_2(t_{pk})$ ，那么每个 $v_2(t_i)$ 就可以确定在一个区间内，对于每个数查询的时候直接判断一下 $v_2(a_i)$ 的值是否在区间内即可

总复杂度 $O(n\log\log n)$

16. ARC142E - Pairing Wizards [Keter]

题面

$n$ 个人，每个人有两个属性 $a_i,b_i$ ，你一次操作可以让某一个人的 $a_i$ 加 1

给定 $m$ 对人 $(x_i,y_i)$ ，你需要进行最少次数的操作，使得对于任意 $i$ 均满足 $(a_{x_i}\ge b_{x_i}\land a_{y_i}\ge b_{y_i})\lor(a_{x_i}\ge b_{y_i}\land a_{y_i}\ge b_{x_i})$

求最少操作次数

$2\le n\le100,1\le a_i,b_i\le100,1\le m\le\frac12n(n-1)$

题解

Sol

首先， $a_{x_i},a_{y_i}$ 要 $\ge\min(b_{x_i},b_{y_i})$ ，需要先用一些操作保证这个事情

接下来，我们考虑还没有被满足的对 $(x,y)$ ，讨论一下一定恰好满足 $[a_x\ge b_x]+[a_y\ge b_y]=1$ ，这启示我们想到二分图~~（想到个锤子啊）~~

假设是 $a_x<b_x$ ，那么 $b_y\le a_y<b_x$ ，也就是要把 $a_x$ 与 $a_y$ 中的一个加到 $b_x$ ，这看起来很网络流~~（真的吗）~~

但是 $a_y$ 加的值不是确定的，因此我们可以考虑对值域拆点，然后使用一些神秘的建图方式（设值域为 $A$ ）：

对每个 $a_i\ge b_i$ 的 $i$ ，连边 $(S\rightarrow i,b_i-a_i)$
对每个 $a_i<b_i$ 的 $i$ ，拆成 $A$ 个点 $(i,1),(i,2),\cdots,(i,A)$ ，连边 $((i,x)\rightarrow (i,x-1),\infty),((i,x)\rightarrow T,1)$
对每个 $(x,y)$ ，设 $a_x\ge b_x$ ，连边 $(x\rightarrow(y,b_x),\infty)$

那么答案就是这张图的最小割

这张图的边数是 $O(n^2+nA)$ ，流量是 $O(nA)$ ，因此总复杂度 $O(n^3A+n^2A^2)$

17. ARC155D - Avoid Coprime Game [Keter]

题面

给定 $a_1,a_2,\cdots,a_n$ ，有两个人在做游戏，有一个整数 $G$ ，初始为 $0$ ，每轮每个人可以进行如下操作：

选择一个 $a_i$ ，使得 $\gcd(G,a_i)\neq1$ ，执行 $G\leftarrow\gcd(G,a_i)$ ，并将 $a_i$ 删除

不能操作者输，求先手如果第一步选 $a_i$ ，之后两人都按最优策略选数，是先手胜还是后手胜

$2\le n,a_i\le2\times10^5$

题解

Sol

降智了。

感性理解一下，当前局面只和当前的 $G$ ，以及此时的先后手有关（也即已经删除的数个数的奇偶性），那么直接 dp

中间需要求是否存在 $x$ 满足 $\gcd(G,x)=d$ ，这个可以莫反，总复杂度 $O(A\log A)$

18. ARC137E - Bakery [Keter]

题面

有 $n$ 天， $m$ 个人，雇佣第 $i$ 个人的代价是 $c_i$ ，雇佣后第 $i$ 个人会在 $[l_i,r_i]$ 内每一天生产一个面包

第 $i$ 天你最多卖出 $a_i$ 个面包，卖出一个面包会产生 $d$ 的收益，面包不能留到之后再卖

求最大收益， $1\le n,m\le2000,1\le l_i,r_i\le n,1\le c_i,d\le10^9$

题解

Sol

这啥啊。

这个东西看起来很流，但我不知道怎么流，于是我看了题解

题解：

点集为 $0,1,\cdots,n$ ，建如下的边：

$(j\rightarrow j-1,(a_j,-d))$
$(j\rightarrow j-1,(m-a_j,0))$
$(l_i-1\rightarrow r_i,(1,c_i))$

答案就是这张图的最小费用循环流

但是最小费用循环流不是很好做，因此我先把前两类边流满，变成如下的图：

$(j-1\rightarrow j,(a_j,d))$
$(j-1\rightarrow j,(m-a_j,0))$
$(l_i-1\rightarrow r_i,(1,c_i))$

然后用 primal-dual 算法跑就可以了，复杂度 $O(n(n+m)\log(n+m))$

19. ARC136E - Non-coprime DAG [Keter]

题面

以 $1,2,\cdots,n$ 为点集建有向图， $i\rightarrow j$ 有边当且仅当 $i<j$ 且 $\gcd(i,j)\neq1$ ，第 $i$ 个点的点权为 $a_i$

求一个集合 $S$ 使得 $S$ 中的点两两不可达且 $\sum_{x\in S}a_x$ 最大，求最大值

$1\le n\le10^6,1\le a_i\le10^9$

题解

Sol

我们先把 1 扔掉。

考虑两个点什么时候可达，那么每走一步相当于选择一个 $p|i$ 然后 $i\leftarrow i+p$

那么这种情况可以考虑一些特殊值，比如我们可以通过 $p=2$ 的情况作为中转，这样两边至多需要一步，看起来就比较优

具体地，设 $f(x)$ 表示 $x$ 的最小质因子， $x$ 和 $y$ 可达当且仅当 $x+[x\nmid2]f(x)\le y-[y\nmid2]f(y)$

那么直接令一个数代表的区间为 $[x-x\nmid2-1),y+y\nmid2-1)]$，问题就是要选出权值和最大的区间使得它们两两有交，也即整体有交，那么区间加后枚举这个交即可

复杂度 $O(n)$

20. ARC135E - Sequence of Multiples [Euclid]

题面

$T$ 组数据。

长为 $N$ 的数列 $A_1,A_2,\cdots,A_N$ 满足如下条件：

$A_1=X$
对于所有 $i$ ， $i|A_i$
$A_1<A_2<\cdots<A_n$

给定 $X$ ，求 $\sum_{i=1}^NA_i$ 的最小值，对 $998244353$ 取模

$1\le T\le10,1\le N,X\le10^{18}$

题解

Sol

$A_i=i\left\lfloor\dfrac{A_{i-1}}{i}\right\rfloor+1$ ，设 $a_i=\dfrac{A_i}i$ ，那么经过变形可以得到 $a_i=a_{i-1}+1-\left\lceil\dfrac{a_{i-1}}i\right\rceil$ ，那么当 $\left\lceil\dfrac{a_{i-1}}i\right\rceil$ 一定时，我们就可以快速跳过一部分

$A_i$ 的增长实际上比较缓慢，可以认为是 $O(X)$ 的，那么 $\left\lceil\dfrac{a_{i-1}}i\right\rceil=\left\lceil\dfrac{A_i}{i^2}\right\rceil$ ，当 $i\le O(\sqrt[3]X)$ 时最多只有 $O(\sqrt[3]X)$ 种，当 $i>O(\sqrt[3]X)$ 时值域是 $O(\sqrt[3]X)$ 的，因此只有 $O(\sqrt[3]X)$ 种，所以我们可以 $O(1)$ 跳过每一段，然后就可以以 $O(T\sqrt[3]X)$ 的复杂度完成本题

事实上，当 $X=10^{18}$ 时， $\left\lceil\dfrac{A_i}{i^2}\right\rceil$ 大约有 1.8e6 种

21. AGC057C - Increment or Xor [Keter]

题面

给定长为 $2^n$ 的 $0\sim 2^n-1$ 的排列 $a_0,a_1,\cdots,a_{2^n-1}$ ，你要用如下两种操作将其变为 $0,1,2,\cdots,2^n-1$ ，或者报告无解：

对于所有 $i$ ， $a_i\leftarrow(a_i+1)\pmod{2^n-1}$
选定一个 $x$ ，对于所有 $i$ ， $a_i\leftarrow a_i\oplus x$

$1\le n\le18$ ，操作序列长度 $\le10^6$

题解

Sol

$+1$ 和 $\oplus x$ 的操作好像有一个套路，就是倒序建 trie，即从低到高考虑二进制位

那么 $\oplus x$ 就是将某些层的所有点的儿子交换， $+1$ 就是将从根节点开始走 $1$ 走出的路径上的所有点的儿子交换

因此我们可以考虑套用过来，我们首先把序列重新排一下序，将原来下标为 $x$ 的数放到 $\text{rev}(x)$ 的位置，然后按这个序列进行操作，这样我们只要让 trie 的每个节点都是左儿子 0 右儿子 1 即可

我们有如下的一种操作：

选择一个点，先将它异或成 $2^n-1$ ，然后执行 $+1$ 操作，这样我们就在整体异或上一个数的前提下对到根的某条路径全部交换儿子

如果我们对 $0,2,4,\cdots,2^n-2$ 分别做一次这个操作，其效果就相当于 $\oplus 2^{n-1}$ ，因此我们可以钦定我们在 $\oplus x$ 时， $x$ 的第 $n-1$ 位为 $0$ ，这样就只有这个操作能够改变最后一层的状态了，也就可以得知有哪些位置需要进行这个操作，模拟一下，最后判断是否能再进行一次 $\oplus x$ 操作得到答案即可

复杂度 $O(n2^n)$ ，操作次数 $O(2^n)$

22. AGC047D - Twin Binary Tree [Keter] ⭐

题面

有两棵 $2^n-1$ 个节点的满二叉树，给定 $0\sim 2^{n-1}-1$ 的一个排列 $p_i$ ，表示从第一棵树的第 $i$ 个叶子向第二棵树的第 $p_i$ 个叶子连无向边，称这些边为绿边

求这张图中恰好经过两条绿边的所有简单环的点编号乘积之和，对 $10^9+7$ 取模

$2\le n\le18$

题解

Sol

考虑枚举其中一个点 $u$ ，再枚举两个树中的 lca，最多有 $O(n\log^2n)$ 组，那么我们就是要求出同时属于两棵子树的所有点的权值和，但这好像不能 $O(1)$ 做

因此，我们考虑换一种枚举方式，我们枚举其中的一个 lca，设其为 $u$ ，然后统计 $a$ 到每个 $c$ ， $b$ 到每个 $d$ 的路径权值：

不难发现， $\sum #c$ 和 $\sum#d$ 都是 $O(n\log^2n)$ 的，因此我们可以直接暴力向下搜索，然后以 $O(#c)$ 的时间统计答案，总时间复杂度就是 $O(n\log^2 n)$ 的

23. AGC051C - Flipper [Euclid]

题面

有一个 $10^9\times10^9$ 的方格，其中 $(x_1,y_1),(x_2,y_2),\cdots,(x_n,y_n)$ 的格子是黑色的，其余格子都是白色的

你可以选择任意一个 $2\times3$ 的区域，将其中所有格子反色

求经过若干次操作后，最少有多少个黑色格子

$1\le n\le10^5$

题解

Sol

两个局面等价的充要条件是：每列的黑色格子奇偶性分别相等，并且每行 $\bmod3=x$ 的奇偶性三个相等或三个相反

必要性考虑单次操作即可，充分性可以把任意局面消元至只有最后两列和最后一行有黑格

那么问题转化为，我们现在有 $A,B,C$ ，并且有 $X$ 个 $(1,0,0)$ ， $Y$ 个 $(0,1,0)$ ， $Z$ 个 $(0,0,1)$ ，你可以反转一些向量，或者添加偶数个同种向量，最后你需要最小化 $\max(A,cnt_0)+\max(B,cnt_1)+\max(C,cnt_2)$ ，其中 $cnt_i$ 表示第 $i$ 个位置上向量，需要保证 $cnt_i$ 与对应的 $A/B/C$ 奇偶性相等

观察到最多反转一种向量，然后这个问题可以 $O(1)$ 解决

总复杂度 $O(n\log n)$ 或 $O(n)$

24. AGC033D - Complexity [Keter] ⭐

题面

给定一个 $n\times m$ 的矩阵，每个格子是白色或者黑色

按照如下方式定义一个矩阵的权值：

如果矩阵所有格子颜色相同，则权值为 $0$
否则，选一条横线或者竖线将这个矩形切开，令剩下两个矩形的权值为 $c_1,c_2$ ，则原矩形的价值为 $\min\max(c_1,c_2)+1$

对给定矩阵，求其权值

$1\le n,m\le185$ ，5s，512MB

题解

Sol

你但凡多想一会.jpg

考虑一种策略是将矩阵切成 $1\times1$ 的方格，而这最多需要 $\log_2n+\log_2m$ 次

因此，答案最多是 $\log$ 级别的

那么我们定义 dp 状态 $dp_{o,i,j,k}$ ，满足左上角为 $(i,k)$ ，右下角为 $(j,x)$ 的矩阵权值为 $o$ 的最大的 $x$

当 $o,i,k$ 一定时，转移点关于 $j$ 单调，因此可以 $O(1)$ 转移

总复杂度 $O(n^3\log n)$

24. AGC035F - Two Histograms [Keter] ⭐

题面

有一个 $n\times m$ 的方格，每个格子都有一个数，初始为 $0$

现有 $k_1,k_2,\cdots,k_n$ 和 $l_1,l_2,\cdots,l_m$ ，表示将第 $i$ 行的前 $k_i$ 个格子 $+1$ ，将第 $i$ 列的前 $l_i$ 个格子 $+1$

求能形成多少种本质不同的方格，两个方格本质不同当且仅当某个格子的值不同

$1\le n,m\le5\times10^5$

题解

Sol

考虑什么时候两种操作会对应同一种方格

我们发现 $k_i=j,l_j=i-1$ 和 $k_i=j-1,l_j=i$ 是等价的

那么我们不妨规定这样的情况我们只统计 $k_i=j-1,l_j=i$

可以证明，满足不存在这样的操作序列生成的方格一定是互不相同的，证明可以找到第一个不等的 $k_i$ 然后对图形讨论一下

那么直接容斥即可：

$ans=\sum_{i=0}^{\min(n,m)}(-1)^i\binom ni\binom mii!(m+1)^{n-i}(n+1)^{m-i}$

复杂度 $O(n+m)$

可以瞎猜一猜操作等价的条件，把本质不同局面转化成操作的计数。

25. AGC030C - Coloring Torus [Euclid]

题面

对于一个 $n\times n$ 的 torus（上下左右都循环的矩形）以及一个整数 $k$ ，定义一个合法的填数方案为：

每个格子填 $1\sim k$ 中的一个整数，且每种数至少被用过一次
对于每个 $i,j(1\le i,j\le k)$ ，对于所有填 $i$ 的格子，周围四联通的格子中 $j$ 的数量相同

给定 $k$ ，选择一个 $n(1\le n\le500)$ ，构造一个 $n\times n$ 的 torus 的合法填数方案

$1\le k\le1000$

题解

Sol

对于 $k\le500$ ，可以一行都填一个数，也可以一条循环斜线上填一个数

对于 $k>500$ ，我们可以选择一个偶数 $n$ ，再选一些循环斜线，让它们交替填两种数，这样最多填 $2n$ 种数，仍然满足题目条件

复杂度 $O(n^2)$

26. AGC039E - Pairing Points [Keter] ⭐

题面

圆上有 $2n$ 个点，你需要将其中的点两两匹配，满足按如下方式建图，最后建出来的图是一棵树：

如果有两条匹配边相交，那么就在它们之间连边

现在给出每对点之间是否能匹配，求有多少满足条件的匹配

$1\le n\le20$

题解

Sol

神秘。

我们考虑 $1$ 和哪个点连接，设其为 $a$ ，那么跨过 $(1,a)$ 的边一定互不相交，也就是说删掉 $(1,a)$ 后每棵一定对应着分属两边的两个区间，可以每次转移第一条跨过 $(1,a)$ 的边所属的树

那么我们如下定义状态：

$f_{a,b,c,d}$ 表示 $[a,b]\cup[c,d]$ 的区间形成一棵树，且恰好有一条边从 $[a,b]$ 跨到 $[c,d]$ 的方案数

$g_{a,b,c,d}$ 表示 $[a,b]\cup[c,d]$ 的区间形成若干棵树，并且每棵树都跨过 $[a,b]$ 和 $[c,d]$ 的方案数

那么对于 $f$ ，我们枚举跨过的是哪条边：

$f_{a,b,c,d}=\sum_{p\in [a,b]}\sum_{q\in[c,d]}g_{a,p-1,p+1,b}\times g_{c,q-1,q+1,d}\times A_{p,q}\\$

对于 $g$ ，我们枚举第一棵树的范围是多少：

$g_{a,b,c,d}=\sum_{p\in[a,b]}\sum_{q\in[c,d]}f_{a,p,q,d}\times g_{p+1,b,c,q-1}$

那么总复杂度就是 $O(n^6)$ ，常数较小。

27. AGC048D - Pocky Game [Euclid] ⭐

题面

$t$ 组数据。

有 $n$ 堆石子，分别有 $a_1,a_2,\cdots,a_n$ 个，两人轮流操作

先手每次从最左边的非空堆中拿出若干个石子吃掉，后手每次从最右边的非空堆中拿出若干个石子吃掉，无法操作者输（即所有堆都为空）

求胜者

$1\le t\le100,1\le n\le100,1\le a_i\le10^9$

题解

Sol

考虑一个人的决策，不妨设她要取最左边的堆，如果当前把最左边的堆取完之后是自己胜，那么肯定会取，否则一定不取

而不取时取 $1$ 个一定不会更劣，所以每次要么取 $1$ 个要么取所有的，而石子显然是越多对自己更优，因此我们可以设计 dp 状态：

$dp_{l,r,0}$ 表示 $[l,r]$ 区间内的石子堆， $l$ 左边的一堆石子至少要有多少个，才能使从左边开始取的先手胜

$dp_{l,r,1}$ 表示 $[l,r]$ 区间内的石子堆， $r$ 右边的一堆石子至少要有多少个，才能使从右边开始取的先手胜

转移是 $O(1)$ 的，因此总复杂度 $O(n^2)$

28. AGC032E - Modulo Pairing [Keter]

题面

给定 $2n$ 个数 $a_1,a_2,\cdots,a_{2n}$ ，要求将这些数匹配成 $n$ 对数对 $(a_{x_i},a_{y_i})$ ，求 $\max((a_{x_i}+a_{y_i})\bmod m)$ 的最小值

$1\le n\le10^5,1\le m\le10^9,0\le a_i<m$

题解

Sol

我们将 $a$ 排序，对于一对数，如果它们的和 $\ge m$ ，那么在它们之间连红边，否则连蓝边，那么一定有一个最优解形如以下形式：

证明的话，讨论两个区间的位置关系，有如下若干种情况：

均可以进行调整。

那么我们现在只要找到分界点即可。

注意到我们希望这个分界点越往左越好，而每个数 $a_i$ 在左边或者在右边都会对配对的数有一个范围限制，所以可以根据这个求出分界点的范围区间，那么只要取最左边的即可

复杂度 $O(n\log n)$

29. AGC028D - Chords [Keter] ⭐

题面

圆周上有 $2n$ 个点，你要将它们匹配成 $n$ 对，在一对匹配点之间连线段，有 $k$ 对已经配好 $(a_i,b_i)$

求所有配对方式，线段形成的连通块数之和，对 $10^9+7$ 取模

$1\le n\le300$

题解

Sol

感觉，这个，很厉害啊！

考虑一个连通块一定有一个点下标的最大值和最小值

我们令 $dp_{i,j}$ 表示只考虑 $[i,j]$ 中的点怎么连时， $i,j$ 是连通块最小值/最大值的方案数（注意可以有多个连通块，但我们只要求 $i,j$ 属于同一个连通块）

考虑 $x$ 个点之间乱连的方案数是 $(x-1)\times(x-3)\times\cdots1$ （ $x$ 为奇数的话是 $0$ ），设其为 $g(x)$

那么我们可以使用容斥来算 $dp_{i,j}$ ，显然 $[i,j]$ 中的点不能向 $[i,j]$ 外连，那么我们有：

$dp_{i,j}=g(c[i:j])+\sum_{k=i+1}^{j-1}dp_{i,k}\times g(c[k+1:r])$

其中 $c[l:r]$ 表示 $[l,r]$ 中还没有被确定的点数，即不包含在那 $k$ 个对中的点数

注意特判 $[i,j]$ 内已经有点被钦定向外连的情况

复杂度 $O(n^3)$

这个给每个连通块找到一个“特征值”，再对所有同一特征值进行计数，好神奇啊。

30. AGC027F - Grafting [Euclid]

题面

$t$ 组数据。

给定两棵 $n$ 个点的树 $A,B$ ，点有编号

$A$ 中的点有颜色，初始都为白色，你每次操作可以将 $A$ 中的一个白色叶子（这里定义为度数为 $1$ 的点）接到 $A$ 中其他点下面，并将其染黑

求是否能让 $A$ 和 $B$ 的在编号上相同（即对于任意一条连接编号为 $u$ 和 $v$ 的点的边，其要么在 $A$ 和 $B$ 中都出现，要么都不出现）

$1\le t\le20,3\le n\le50$

题解

Sol

虽说我好像没看题解，但是我看数据了，所以不知道算不算我自己做出来的。

但是标 Keter 还是太给这题脸了。

考虑如果有操作不动点，那么我们直接以这个点开始模拟即可，具体地，可以根据两棵树的父子关系建一张先后顺序图，然后判断这张图是不是 DAG 即可

但是这题的难点在于意识到答案有可能 $=n$ ，也即没有不动点，考虑这样的情况一定是我们选定一个点，然后第一个黑点接在这个点上，并且接下来所有的黑点都接在黑点上，证明比较容易

那么我们直接再枚举一个根调用上面的算法即可，复杂度 $O(tn^3)$

31. AGC033F - Adding Edges [Keter] ✨

题面

给定一棵 $n$ 个点的树 $T$ ，以及一个 $n$ 个点 $m$ 条边的无向图 $G$

对于 $G$ 中的两条边 $(a,b)$ 和 $(b,c)$ ，如果 $(a,c)$ 这条边不存在，且 $T$ 中有一条链以某种顺序包含 $a,b,c$ ，那么在 $G$ 中加入 $(a,c)$ 这条边

求当无法继续加边时 $G$ 中有多少边

$2\le n\le2000,1\le m\le2000$

题解

Sol

我们可以将 $G$ 中每条边视为 $T$ 上的路径，对于 $T$ 中一条路径上顺次出现的 $a,b,c$ ，如果 $(a,b)$ 和 $(a,c)$ 同时在 $G$ 中，我们可以把 $(a,c)$ 变为 $(b,c)$

不断这样操作，那么在最后的图 $G^\prime$ 上一定满足：

$(x,y)$ 会被加入到 $G$ 中当且仅当存在 $v_1,v_2,\cdots,v_k$ 使得 $(x,v_1),(v_1,v_2),(v_2,v_3),\cdots,(v_{k-1},v_k),(v_k,y)$ 都在 $G^\prime$ 中，并且存在一条路径依次经过 $x,v_1,v_2,\cdots,v_k,y$

证明的话考虑 $x-y$ 这条路径， $G^\prime$ 上一定走不了“回头路”

那么现在问题就是如何进行这个 “缩边” 的过程：

我们定义 $f(x,y)$ ，表示任意一个 $k$ 使得 $k$ 在 $x-y$ 路径上且在 $G^\prime$ 上 $x$ 与 $k$ 联通，如果不存在则 $f(x,y)=0$

依次加入给出的所有边，假设当前加入 $(x,y)$ ：

$f(x,y)=y$ ，那么显然没必要继续加了，直接退出
$f(x,y)\neq0$ ，这说明存在一条更小的边，会把 $(x,y)$ 拆开，我们再加入 $(f(x,y),y)$ 即可
$f(y,x)\neq0$ ，同上
$f(x,y)=0\land f(y,x)=0$ ，那么我们可以加入这条边，加入这条边后我们需要更新 $x,y$ 子树中的 $f$ 值，那么我们 dfs 进去，假设当前考虑的是 $x$ 子树中的 $z$ ，那么如果 $f(y,z)=0$ ，我们需要将 $f(y,z)$ 赋值为 $x$ ，否则，说明 $(f(y,z),y)$ 有边，并且这条边会被 $(x,y)$ 拆开，我们将 $(f(y,z),x)$ 加入待加入的边的队列，而 $z$ 子树中的 $f(y,?)$ 一定都有值，这个值不会因新加入的边而变得错误，因此可以直接退出当前的 dfs

考虑复杂度，我们每次 dfs 会将一个 $f(y,z)=0$ 的位置赋一个非零的值，或者新缩一条边

一个 $f$ 被赋为非零的值后不会再变为 $0$ ，所以这个操作最多 $O(n^2)$ 次

一条边最多被缩 $n$ 次，所以这个操作最多 $O(nm)$ 次

因此总复杂度为 $O(n^2+nm)$

32. AGC017E - Jigsaw [Keter]

题面

有 $n$ 块拼图，以及常数 $h$ ，第 $i$ 块的形状由 $a_i,b_i,c_i,d_i$ 描述，表示它按平面直角坐标系建系时，包含 $(1,c_i+1\sim c_i+a_i),(2,1\sim h),(3,d_i+1\sim d_i+b_i)$ 这些格子

现在你可以对这些积木进行平移，使得每个积木的 $(2,1)$ 格子的 $y$ 坐标都为 $1$ ，并且对于任意其他格子 $(x,y)$ ，要么 $y=1$ ，要么 $(x,y-1)$ 也被某个格子覆盖

求是否可能

$1\le n\le10^5,1\le h\le200,0\le a_i,b_i,c_i,d_i\le h$

题解

Sol

脑子糊了。

考虑如果我们把每块拼图看成边的话，那就类似于欧拉回路，考虑怎么转化成边

对于每个拼图，我们按照如下方式建有向边：

如果 $c_i=0$ ，那么起点为 $-a_i$ ，否则起点为 $c_i$

如果 $d_i=0$ ，那么起点为 $b_i$ ，否则起点为 $-d_i$

这样我们就是要求若干条从正点到负点的路径，使得所有边都恰好属于一条路径

这很欧拉回路，但又不完全欧拉回路，因此我们可以想象一个虚拟点，把每条路径的末尾连向这个虚拟点，虚拟点再连向这条路径的开头

这说明正点应该满足 $out\le in$ ，负点应该满足 $in\le out$ ，并且对于一个连通块，其必须要有至少一个点满足 $in\neq out$ （由于前面两条性质，这样一定能分别找到一个正点和负点 $in\neq out$ ）

由于一个连通块 $out=in$ ，所以虚拟点一定 $in=out$

那么这样判断一下即可，复杂度 $O(n+h)$

33. AGC044D - Guess the Password [Euclid]

题面

交互题。

有一个长度 $\le L$ 的字符串 $S$ ，所有字符均在 0~9,A~Z,a~z 中

每次你可以询问一个字符串，满足这个字符串长度 $\le L$ 且所有字符均在 0~9,A~z,a~z 中，交互库会告诉你 $S$ 与 $T$ 的编辑距离

你最多可以询问 $Q$ 次，你需要求出 $S$

$L=128,Q=850$

题解

Sol

编辑距离操作太多，显然可能全考虑，所以我们考虑一些极端情况

假设我们询问的是 $L$ 个 F，那么我们返回给我们的一定是 $L-cnt_F$ ，因此我们可以先用 $62$ 次操作求出所有的 $cnt$

编辑距离如果只有插入，说明 $T$ 是 $S$ 的子序列，这对应着 $|T|+ret=|S|$ 的情况

因此，我们可以询问一个串是否是 $S$ 的子序列，那么一种朴素的思路是按字符考虑，我们考虑前 $i$ 个字符组成的子序列，现在要插入第 $i+1$ 个字符，那么依次尝试是否能加进每个空隙即可

但是这样是 $O(L|\Sigma|)$ 的，不太行。

考虑我们合并两个子序列的复杂度是 $O(|a|+|b|)$ ，因此可以分治，每次从中间劈开，最后把两部分合并在一起，这样是 $O(L\log|\Sigma|)$ 的，就可以通过了

34. AGC062B - Split and Insert [Euclid]

题面

有长度为 $N$ 的排列 $A_1,A_2,\cdots,A_N$ ，初始 $A_i=i$

进行 $K$ 次操作，操作有一个代价 $C_i$ ，第 $i$ 次操作你可以选择一个 $k_i$ ，然后排列的后 $k_i$ 个数插入到前 $N-k_i$ 中（不改变相对顺序）

要求最后将 $A$ 变为一个给定的排列，使得 $\sum k_iC_i$ 最小，求这个最小值

$2\le n\le100,1\le k\le100,1\le C_i\le10^9$

题解

Sol

考虑操作倒过来就是选出一个子序列塞到最后面

令 $dp_{x,l,r}$ 表示后 $x$ 次操作，将值域 $[l,r]$ 内的数相对顺序排好的最小代价

转移枚举断点即可，由于代价是 $k_iC_i$ ，可以看成操作的数的个数 $\times C_i$ ，因此可以这样设状态

复杂度 $O(n^4)$

35. AGC062C - Mex of Subset Sum [Keter]

题面

给定 $A_1,A_2,\cdots,A_n$ ，以及一个整数 $K$

求前 $K$ 小的不能被 $A$ 的子集和表示出的数

$1\le N\le60,1\le K\le1000,1\le A_i\le10^{15}$

题解

Sol

交了个暴力就过了，魔幻。

具体地，将 $A$ 从小到大排序，然后依次加入 $A_i$ ，时刻维护出当前所有数的子集和的连续段，如果发现 $A_i$ 以下有 $K$ 个无法表示出的数直接退出

复杂度证明：我们可以说明，在插入 $A_1,A_2,\cdots,A_i$ 后，如果还没有退出， $[0,A_1+A_2+\cdots+A_i]$ 无法表示出的数最多有 $K\times i$ 个

考虑归纳，如果对于 $i-1$ 成立，那么 $[0,A_i)$ 中一定最多 $K$ 个无法表示出，而 $[A_i,A_1+A_2+\cdots+A_i]$ 中一定最多 $K\times(i-1)$ 和无法表示出，因为其中包含 $A_1,A_2,\cdots,A_{i-1}$ 能表示出的所有数 $+A_i$

所以复杂度为 $O(N^2K)$

36. AGC062D - Walk Around Neighbourhood [Keter]

题面

给定 $D_1,D_2,\cdots,D_N$ ，保证 $D_i$ 为偶数

你初始在 $(0,0)$ ，每一次操作你可以选择一个没有被选择过的 $D_i$ ，然后走到一个与当前位置曼哈顿距离为 $D_i$ 的点（不一定是格点）

求 $N$ 次操作后是否能回到 $(0,0)$ ，如果能，求出最小的 $\max(|x_i|+|y_i|)$

$1\le N,D_i\le2\times10^5$

题解

Sol

……？

二分看起来比较有前途。

不管进行什么操作，最后能到的点都是到 $(0,0)$ 曼哈顿距离在某个区间 $[L,R]$ 内

具体地， $[L,R]$ 在操作 $D$ 后会变成 $[\max(0,L-D,D-R),R+D]$

那么加上我们二分的 $M$ 的限制，也就是 $[\max(0,L-D,D-R),\min(M,R+D)]$

因此，我们可以将整个过程分为两个阶段，一个阶段是 $R$ 还没有顶到 $M$ ，一个阶段是 $R$ 顶到了 $M$

我们称 $D>M$ 的操作为 “大步”， $D\le M$ 的操作为 “小步”

那么容易发现第一个阶段最多只有一个 “大步”，即结束的那一步

第二个阶段 “大步” 会让 $L$ 变为 $D-M$ ，“小步” 会让 $L$ 变为 $L-D$ ，讨论一下可知将 $D_i$ 从大到小选最优

那么我们走出来的东西可能有以下若干种情况：

第一阶段没有 “大步”，第二阶段没有 “大步”，这意味着整体没有 “大步”，直接判断最大值是否大于剩余所有值之和即可
第一阶段有 “大步”，第二阶段没有 “大步”，这意味着整体只有一个 “大步”，设其为 $D$ ，如果第一阶段小步和为 $s_1$ ，整体小步和为 $S$ ，那么需要满足 $s_1\le M,D-s_1\le M,S-s_1\le D-M$
第一阶段没有 “大步”，第二阶段有 “大步”，那么需要满足 $s_1\ge M,S-s_1\le D-M$
第一阶段有 “大步”，第二阶段有 “大步”，那么需要满足 $D_1-s_1\le M,S-s_1\le D_2-M$

注意到 $D_1,D_2$ 只用考虑最小的两个 “大步” 即可，而需要我们维护 $\ge k$ 的第一个 “小步” 能凑出来的数，这个可以顺着扫 $M$ ，用 bitset 维护

由于 $\frac {\max D}2\le M\le\max D$ ，所以复杂度为 $O(\frac{D^2}\omega)$

37. ARC160E - Make Biconnected [Euclid]

题面

给定一棵 $n$ 个点的树，点有点权 $w_i$ ，保证每个点度数最多为 $3$

现在要在这棵树中加边， $(i,j)$ 之间加边的代价是 $w_i+w_j$

求将这棵树加成点双连通图的最小代价，构造方案

$3\le n\le2\times10^5$

题解

Flamire 做法

Sol

首先，如果有偶数个叶子，可以说明，能找到一个方案的代价为所有叶子权值之和

具体地，我们任取一个重心，然后每次取属于不同子树的两个叶子在它们之间建边，由于 $\deg_i\le 3$ ，所以这样一定会连成点双

如果有奇数个叶子，我们枚举剩出来的叶子是哪个，设其为 $u$ ，那么除 $u$ 之外的其他叶子可以用偶数的方法连

这时 $u$ 只要连除了它祖先上的若干度数为 $2$ 的点之外的点就可以将图变为点双，因此只要求出剩下部分的 $w$ 最小值即可，这是容易实现的，对每个 $u$ 都做这件事情

复杂度 $O(n\log n)$ 或 $O(n)$

题解做法

Sol

偶数个叶子，可以将叶子按照 dfs 序排序，设其为 $a_1,a_2,\cdots,a_k$ ，然后将 $a_i$ 和 $a_{i+k/2}$ 连边

这样如果我们删除了点 $u$ ，设其度数为 $d$ ，那么剩下的子树一定是 $d$ 个 dfs 序上的区间，而 $d\le3$ ，因此一定通过新加的边联通

奇数个叶子，我们需要多用一个点，我们从小到大依次判断每个点是否能作为新加的点，点 $r$ 能做为新加的点的充要条件是 $r$ 为叶子，或存在两个叶子 $u,v$ ， $LCA(u,v)\neq r$

如果 $r$ 为叶子，我们直接将其他任意一个叶子 $w$ 和 $r$ 连上即可，然后去掉 $w$ ，对剩余叶子跑偶数的情况

如果 $r$ 不为叶子且对于任意叶子 $u,v$ 都有 $LCA(u,v)=r$ ，那么如果某个叶子连 $r$ ，删掉 $r$ 之后图不连通，并且如果这个条件不满足，我们找一对 $LCA(u,v)\neq r$ 的叶子，将 $r$ 与 $u$ 连边，那么一定能形成点双

因此我们直接考虑全局最小值，由于 $d\le3$ ，若上述条件不满足，那么这个点一定是全局最小值伸出去三条链，这时次小值一定符合条件

复杂度 $O(n\log n)$ 或 $O(n)$

38. AGC029E - Wandering TKHS [Safe]

题面

给定一棵 $n$ 个点的树，有一个人初始在 $r$ ，她每次会从她访问过的所有点的邻点中选一个还没访问的下标最小的点访问

对 $r=2,3,\cdots,n$ ，求她访问到 $1$ 时访问了多少个点

$1\le n\le2\times10^5$

题解

Flamire 做法

Sol

考虑对于每个 $u$ ，它能贡献到哪些 $r$

我们把 $1$ 到 $u$ 的路径找出来，以 $1$ 为根，那么对于一个 $v$ ，当且仅当 $lca(u,v)=y$ ， $y$ 满足 $1$ 到 $y$ 的路径（不含 $y$ ）最大值大于 $y$ 到 $u$ 的路径

由于这个是单调的，直接倍增即可，复杂度 $O(n\log n)$

题解做法

Sol

同上，但是考虑 $1$ 到 $u$ 的最大值 $A$ ，在 $A$ 上方的点一定不会访问到，在 $A$ 下方的点一定会访问到，因此只有 $A$ 不确定，那么处理路径最大值和次大值就可以做到 $O(n)$

39. PA2021 - Od deski do deski [Keter] ⭐

题面

给定 $n,m$ ，求满足如下条件的长为 $n$ 的序列数量：

值域为 $[1,m]$ 内的整数
每次删除一个两端相同的子段（长度 $\ge2$ ），该序列能在若干次操作内删空

答案对 $10^9+7$ 取模

$1\le n\le3000,1\le m\le10^9$

题解

Sol

这 nm 蓝题？？？我是不是退化了。

考虑怎么判断一个序列是否能删空。一个显然的 dp 是令 $h_i$ 表示前 $i$ 个数组成的数列是否能删空，那么转移是 $h_i\leftarrow h_{j-1}[a_j=a_i]$

我们进行一个类似 dp 套 dp 的东西，令 $f_{i,j}$ 表示长为 $i$ 的无法删空的序列，且有 $j$ 个 $x$ 满足存在 $h_{k-1}[a_k=x]=1$ 的方案数， $g_{i,j}$ 表示长为 $i$ 的可删空的序列，且有 $j$ 个 $x$ 满足存在 $h_{k-1}[a_k=x]=1$ 的方案数

有转移：

$\begin{aligned}j\times f_{i,j}&\rightarrow g_{i+1,j}\\(m-j)\times f_{i,j}&\rightarrow f_{i+1,j}\\j\times g_{i,j}&\rightarrow g_{i+1,j}\\(m-j)\times g_{i,j}&\rightarrow f_{i+1,j+1}\\\end{aligned}$

复杂度 $O(n^2)$

40. NOI2018 - 你的名字 [Keter] ✔️

题面

给定小写字符串 $s$ ， $q$ 次询问，每次询问给定字符串 $t$ 和 $[l,r]$ ，求 $t$ 有多少本质不同的子串在 $s[l:r]$ 中没有出现

$1\le|s|\le5\times10^5,q\le10^5,\sum|t|\le10^6$

题解

Sol

可以转化为求 $s[l:r]$ 与 $t$ 的本质不同的公共子串个数

那么可以考虑计算 $t$ 的每个前缀与 $s[l:r]$ 的最长公共后缀 $pre_i$ ，但是这样有可能算重，所以我们对 $t$ 建 sam，然后对于 sam 上的每一个节点 $O(1)$ 通过 $pre$ 求出公共子串个数

那么现在需要解决的问题就是 $t$ 的每个前缀与 $s[l:r]$ 的最长公共后缀

如果 $s[l:r]$ 是给定的，那么我们直接对它建 sam，然后把 $t$ 放在上面跑匹配，并维护一个当前长度即可

现在 $s[l:r]$ 不是给定的，并且注意到由于有 $[l,r]$ 的限制，所以 $s$ 中同一个节点上的字符串可能有的存在有的不存在，也就是说，在对 $t$ 跑匹配的时候，如果失配那么只能一个一个减长度（--len）

现在要解决的就是对于 $s$ 的 sam 中节点 $x$ 长为 $len$ 的字符串，查询 $len+c$ 在 $s[l:r]$ 中是否存在

如果存在，那么必定在 $x$ 的 $c$ 出边指向的节点 $y$ 里，这意味着原问题等价于查询 $y$ 是否存在 $[l+len,r]$ 中的 endpos

那么这个我们可以在 sam 的 fail 树上进行权值线段树合并维护 endpos，注意需要可持久化

那么总复杂度就是 $O(\sum|t|\log|s|)$

41. PA2019 - Desant [Keter] ⭐

题面

给定排列 $a_1,a_2,\cdots,a_n$ ，对 $k=1,2,\cdots,n$ ，求包含恰好 $k$ 个元素的子序列的逆序对数最小值，并求取到最小值的逆序对数数量

$1\le n\le40$

6s, 768MB

题解

Sol

这种题对 oi 来说还是为时太早了一些。

这个 $n\le40$ 看起来很恐怖，但经过上面的题的毒打，我已经不敢断定它是不是指数了！

于是我点开了题解。

题解：对于长为 $i$ 的前缀，我们只需要知道 $a_1,a_2,\cdots,a_i$ 中选的子序列在被 $a_{i+1},a_{i+2},\cdots,a_n$ 划分的值域区间中，每个区间包含了多少个，就可以转移了

这样我们的复杂度是 $\prod b_i$ ，满足 $\sum b_i\le n$ ，那么似乎最优的是 $b_i$ 全 $=3$ ，再选 $O(1)$ 个 $2$ ，转移解码是 $O(n)$ 的，因此总复杂度 $O(n^23^{n/3})$

42. CF1830C - Hyperregular Bracket Strings [Keter] ⭐

题面

一个长为 $n$ 的合法括号串 $s$ ，我们有 $k$ 个区间 $[l_i,r_i]$ ，对于 $i=1,2,\cdots,k$ ， $s$ 满足 $s[l_i:r_i]$ 是合法括号串

求满足条件的括号串个数，对 $998244353$ 取模

$1\le n\le3\times10^5,0\le k\le3\times10^5$

题解

Sol

如果有 $i,j$ 满足 $l_i\le l_j\le r_i\le r_j$ ，那么我们可以将它们拆成 $[l_i,l_j-1],[l_j,r_i],[r_i+1,r_j]$ 三个区间，这三个区间都需要是合法括号串

这样之后，剩下的区间一定形成一个树形结构

如果有 $i,j$ 满足 $l_i\le l_j\le r_j\le r_i$ ，那么我们可以将它们拆成 $[l_j,r_j]$ 和 $[l_i,r_i]-[l_j,r_j]$ ，这些部分内部也需要是合法括号串

所以如果我们建出了这棵树，我们可以直接查询它有多少它的子树没有包含的元素，那么这部分一定要组成合法括号串，调用卡特兰数即可

但问题在于我们建不出这棵树，我们观察操作，发现两个位置最后属于同一个合法括号串当且仅当经过它们的区间集合一样

那么我们给每一个区间随机一个权值，然后算经过每个点的区间权值异或即可，复杂度 $O(n)$

43. CF1830D - Mex Tree [Euclid]

题面

一棵 $n$ 个点的树，你要给每个点赋 $\{0,1\}$ 中的点权，求 $\sum\limits_{1\le u\le v\le n}\text{mex}(\text{path}(u-v))$ 的最大值

$1\le n\le2\times10^5$

3s, 256MB

题解

Sol

考虑最少会从 $n(n+1)$ 向下浪费多少

一个大小为 $x$ 的 0-连通块会浪费 $\frac12x(x+1)$ ，一个大小为 $x$ 的 1-连通块会浪费 $x(x+1)$

显然有一个解是黑白染色，而这个的上界是 $\left\lfloor\dfrac32n\right\rfloor$ ，说明我们连通块的大小只能是 $O(\sqrt n)$ 级别的，这样就可以记到状态里了

那么现在这就是一个树形背包了，时间复杂度就是 $O(n\sqrt n)$ 的，但空间复杂度是 $O(n\sqrt n)$ 的，这就很伤心。

有两种优化方式：

[1]

注意到我们可以从儿子推到父亲后儿子就没用了，因此我们可以从子树向上合并，每次合并完一堆儿子就把它们全部清空，这样我们时刻需要存的状态都是若干个子树不交的节点的 dp 值，而这样最多 $O(n)$ 的状态

[2]

对于一个节点 $u$ ，我们要存的只有祖先中还没有满足 $u$ 不在第一个遍历的子树中的，也就是我们要记录所有 $u$ 祖先中经过的不是第一个搜索的边的条数个节点的状态

那么我们每次先搜重儿子，这样空间复杂度就是 $O(\sqrt n\log n)$ 的

44. ARC161E - Not Dyed by Majority (Cubic Graph) [Keter] ⭐

题面

$T$ 组数据

给定一张 $n$ 个点的无向联通图，保证每个点度数恰好为 $3$ ，定义对包含 BW 字符的字符串 $s$ ，定义 $f(s)$ ： $f(s)_i$ 为与 $i$ 相连的所有点的 $s_i$ 的众数

请你构造 $t$ 使得不存在 $f(s)=t$ ，无解则输出 -1

$\sum n\le5\times10^4$

题解

Sol

总之，不知道为什么，好像一定有解，并且打一个表可以发现合法的情况还挺多。

editorial 说合法情况在 $n\ge416$ 时大概占 $\frac34$ 左右， $n<416$ 时最少占 $\frac3{16}$

那么我们可以考虑直接随一个然后判断是否合法，这个我们可以将每一个节点上的限制看成 2-sat，然后判断是否有解即可

复杂度 $O(Cn)$ ， $C$ 是一个常数

45. ZJOI2019 - 麻将 [Keter] ✔️

题面

有 $4n$ 张麻将牌，每张麻将是二元组 $(w,t)$ ，其中 $(1\le w\le n,1\le t\le4)$ ，麻将牌两两不同

如果两张麻将的 $w$ 相等，则称它们组成一个对子，如果三张麻将的 $w$ 分别为 $i,i,i$ 或 $i,i+1,i+2$ ，则称它们组成一个面子

一个麻将的集合能够胡当且仅当其大小为 $14$ ，且满足以下两个条件中的一个：

可以被划分为七个 $w$ 值两两不同的对子
可以被划分为一个对子和四个面子

现在你有 $13$ 张牌，这 $13$ 张牌给定，剩下的牌被随机打乱成一个排列

你将依次摸取这些牌，求你第一次存在一个胡牌子集时，摸牌数量的期望，对 $998244353$ 取模

$1\le n\le100$

题解

Sol

你真的以为你会 dp 套 dp 吗.jpg

称 $i,i,i$ 的面子为竖面子， $i,i+1,i+2$ 的面子为横面子

这种题一般先考虑 dp，再搜出自动机，最后在自动机上 dp

考虑如何判断一堆牌是否有一个子集能胡，有一种 dp 是 $dp_{i,j,k,0/1}$ 表示当前我们考虑完了前 $i$ 种 $w$ ，并且留下了 $j$ 个 $(i-1,i)$ 必须组横面子，留下了 $k$ 个单独的 $i$ 必须组横面子，并且当前有没有组过对子，此时最多组成的面子数

那么转移时，假设新加进来一种有 $x$ 个的 $w$ ，那么一定有 $j+k$ 要和前面留下的东西组合，然后剩下的可以枚举预留多少给后面组横面子，剩下的尽量组竖面子

注意到我们可以把 $3$ 个相同的横面子替换为竖面子，因此 $j,k\le2$ ，而又由于我们判胡牌只需要判断 dp 值是否 $\ge4$ ，所以 dp 值 $\le4$

接下来考虑如何建自动机。

$i$ 很大，所以我们可以把 $i$ 放出去，作为在自动机走路的阶段

那么我们现在状态只剩下有多少 $\ge2$ 的数和两个 $3\times3$ 的 dp 值矩阵，那么直接将这样的状态全部搜索出来，枚举下一个数出现了多少次（这里可以把胡牌的状态都并到一起来压状态数）

写一下发现，状态数是 $2092$ 。不要尝试理解 dp 套 dp 的复杂度。

下一步就是在自动机上 dp。

我们的阶段就是刚才扔出来的 $i$ ，即考虑的牌种数，如果抽出 $i$ 张牌仍未胡牌的概率为 $g_i$ ，那么答案就是：

$\dfrac{\sum_{i=0}^{4n-13}g_i\cdot i!\cdot(4n-13-i)!}{(4n-13)!}$

现在就要求 $g_i$ ，令 $f_{i,j,k}$ 表示当前考虑了前 $i$ 种 $w$ ，抽出了其中的 $j$ 张牌，走到了自动机上的 $k$ 号节点，转移是比较容易的

由于同一个 $w$ 的牌互不相同，所以还需要乘上组合数

最后复杂度是 $O(2092n^2)$