task5

[TOC]

1. CF1746F - Kazaee [Keter] ⭐

题面

给定数列 $a_1,a_2,\cdots,a_n$，$q$ 次操作，每次操作为以下两种中的一种：

• 给定 $i,x$，执行 $a_i:=x$
• 给定 $l,r,k$，判断对于任意 $x$，是否都有 $x$ 在 $a[l:r]$ 中的出现次数为 $k$ 的倍数

$1\le n,q\le3\times10^5$

题解

Sol

这个，很不可做啊！

所以不应该想靠谱做法。

注意到，如果我们随机选择一部分数，算它们的出现次数之和，如果该询问答案为“是”，那么出现次数之和一定还是 $k$ 的倍数，否则至少有 $\frac12$ 的概率不是 $k$ 的倍数

因此多次选择值域子集即可，剩下的问题就是统计区间中 1 的个数，树状数组容易维护

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

---

2. CF1696F - Tree Recovery [Keter] ⭐

题面

有一棵你不知道的树，你知道它有 $n$ 个节点，并且对于任意 $i,j,k$，你知道 $dis(i,j)$ 是否等于 $dis(j,k)$

请构造一棵符合条件的树或判断无解。

$1\le n\le100$

题解

Sol

如果确定了一条边，那么可以直接唯一确定整棵树

那么直接暴力枚举 $1$ 和谁相连，然后将树建出来判断是否合法即可

复杂度 $O(n^3)$

---

3. CF1738G - Anti-Increasing Addicts [Euclid]

题面

给定 $n\times n$ 的网格，有些格子可以染黑，有些格子不能染黑

给定 $k$，你需要染黑恰好 $(n-k+1)^2$ 个格子，使得不存在没涂黑的格子 $(x_1,y_1),(x_2,y_2),\cdots,(x_k,y_k)$ 使得 $x_1<x_2<\cdots<x_k$ 且 $y_1<y_2<\cdots<y_k$

给出方案或判断无解

$2\le k\le n\le1000$

题解

Sol

首先将 $k\leftarrow k-1$。

这样每条左上-右下的斜线最多只能留白 $k$ 个，算一下留白的上界是 $(n-k)^2$，这意味着我们不能浪费任何一个格子

我们把不能染黑的格子，以及左下角的长为 $k$ 的阶梯与右上角长为 $k$ 的阶梯称为不能染黑的点

定义每个不能染黑的点 $(x,y)$ 的权值为：所有满足 $i<x,j<y$ 的不能染黑的点 $(i,j)$ 的权值最大值 $+1$

如果存在一个点的权值 $>k$ 显然无解，否则一定可以构造出解，具体地，对每个 $i\in[1,k]$，从最左下的权值为 $i$ 的点开始，优先向右走，不能向右走则向上走，可以走出来一条只向右或向上的包含所有权值为 $i$ 的点的路径，将这条路径全部染黑即可

不难发现 $k$ 条路径都不会有相交

复杂度 $O(n^2)$

---

4. CF1637F - Towers [Keter]

题面

给定一棵 $n$ 个点的树，点有点权 $a_i$，你需要在树上建塔，一个点可以建任意多个塔，你可以给塔任意指定权值 $e$

对每个点 $i$，需要满足存在两个塔 $x,y$，使得 $i$ 在 $x$ 和 $y$ 的路径上，并且 $\min(e_x,e_y)\ge a_i$

求 $\sum e$ 的最小值

$2\le n\le2\times10^5,1\le a_i\le10^9$

题解

Sol

可以证明，所有塔都一定在叶子上。

首先，每个叶子上一定要有塔，否则叶子的限制无法满足。

其次，如果一条路径上有 $x-y-z$ 的塔，我们令 $e_x\leftarrow\max(e_x,e_y)$，并把 $y$ 拆除，一定不会更劣

那么我们只需要确定每个叶子的 $e$ 大小即可

那么由外向内贪心即可

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

---

5. AGC053C - Random Card Game [Keter] ✔️

题面

有 $2n$ 个数，将这些数随机分进两个排列 $a_1,a_2,\cdots,a_n$ 和 $b_1,b_2,\cdots,b_n$

每一回合你可以选择 $1\le k\le\min(|a|,|b|)$，并将 $a_k$ 和 $b_k$ 中较小的从所在排列中删去，后面的递补

定义 $f(a,b)$ 为将至少一个排列删空的最小回合数

求 $f(a,b)$ 的期望，对 $10^9+7$ 取模

$1\le n\le 10^6$

题解

Sol

考虑 $f(a,b)$ 怎么求，不含有 $2n$ 的排列一定会被删空，我们只要最小化含有 $2n$ 的排列删的数量即可

不妨设 $b$ 含有 $2n$，对于一个 $a_i$，设 $j$ 为最小的满足 $b_j>a_i$ 的数，那么有一个下界是 $\max(j-i)$，事实上，这个下界也很容易取到

最大值，差分一下，转化成小于某数，具体地，定义 $f(d)$ 表示所有 $j-i\le d$ 的概率，那么要求的就是 $2n-\sum_{d=0}^nf(d)$

$j-i\le d$ 成立当且仅当每个 $a_i$ 都不是 $a[1:i]\cup b[1:\min(n,i+d)]$ 的最大值，因此概率可以通过 $\prod_{i=1}^{n-d}\frac{2i+d-1}{2i+d}\times\prod_{i=n-d+1}^n\frac{n+i-1}{n+i}$ 来计算

前缀积优化容易做到 $O(n)$ 或 $O(n\log n)$

---

6. AGC052C - Nondivisible Prefix Sums [Keter] ⭐

题面

给定 $n$ 和质数 $p$，求有多少值域为 $[1,p-1]$ 的整数序列 $a_1,a_2,\cdots,a_n$ 满足：存在一种方式将 $a$ 重排使得任意前缀和都不是 $p$ 的倍数

答案对 $998244353$ 取模

$1\le n\le5000,2\le p\le10^8$

题解

Sol

考虑什么样的序列 $a$ 不满足条件

首先总和是 $p$ 的倍数的情况是显然的，我们先不考虑

直觉上来说，一个数不能出现太多次，那么我们考虑众数，可以通过乘逆元使得序列中 $1$ 的出现次数最多

结论：设序列中剩下的数为 $b_1,b_2,\cdots,b_k$，那么该序列不满足条件当且仅当 $1$ 的个数超过 $(p-1)+\sum_i(p-b_i)$

必要性比较显然，考虑充分性如何证明

按照如下方式构建，一定能构造出解：

设当前众数为 $x$，当前前缀和为 $cur$，如果 $p\nmid cur+x$，那么直接在序列后面加上 $x$，否则任选一个其他数 $y$，在后面加上 $y,x$

这个算法出问题只有可能是第二步中，选不出其他的数 $y$，也即此时只剩 $x$，那么由于一开始 $1$ 是众数，容易发现经过上面的算法，$1$ 一直是众数

那么我们的序列形如 $(p-1)\times1,b_1,(p-b_1)\times1,b_2,\cdots,b_k,(p-b_k)\times 1$，而此时还有剩余的 $1$，违反了我们的假设，因此充分性得证

满足条件的情况不好统计，我们用和不为 $p$ 倍数的序列，减去和不为 $p$ 的倍数且众数出现次数过大的序列

可以假设众数为 $1$，然后把算出来的结果 $\times(p-1)$

那么我们需要知道 $(p-1)+\sum_i(p-b_i)$，记到 dp 状态里即可

令 $dp_{i,j}$ 表示 $i$ 个数，$\sum_i(p-b_i)=j$，由于不合法，所以只用考虑 $j\le n$ 的

那么前缀和优化一下就是 $O(n^2)$ 的

---

7. AGC019E - Shuffle and Swap [Euclid]

题面

给定两个 01 串 $A,B$，保证 $A$ 与 $B$ 中 0 和 1 的个数均相等

设 $A$ 中的 1 的位置分别为 $a_1,a_2,\cdots,a_k$，$B$ 中的 1 的位置分别为 $b_1,b_2,\cdots,b_k$

对于 $1,2,\cdots,k$ 的排列对 $(p,q)$，定义 $f(p,q)$ 为：对 $i:1\rightarrow k$，依次执行 $\text{swap}(A_{p_i},A_{q_i})$，得到的最后的 $A$

求有多少 $(p,q)$ 满足 $f(p,q)=B$，对 $998244353$ 取模

$1\le|A|=|B|\le10000$

题解

Sol

显然，可以只考虑 $(a_i,b_i)$ 二元组 $(1,1),(0,1),(1,0)$ 个数分别是多少，而 $(0,1)$ 与 $(1,0)$ 的个数相等

这启发我们记到状态 $dp_{i,j}$ 里，然后讨论第一步的交换

我们发现只有几个不能 $O(1)$ 转移的情况，即 $(1,1)$ 与 $(1,1)$ 交换，可能涉及许多 $(1,1)$ 的数对

但这个转移只在 $(1,1)$ 内部，因此我们可以再进行一个 $O(n^2)$ 的 dp，求出 $f_{i,j}$，从而把初值直接赋在 $dp_{i,0}$ 上

复杂度 $O(n^2)$

---

8. BJWC2018 - Border 的四种求法 [Keter] ✔️

题面

给定一个字符串 $s$，$q$ 次询问，每次给出 $l,r$，求 $s[l:r]$ 的最大 border

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

题解

Sol

对于 $lr$，其中$lcp(l,p)$表示以$l$和以$p$ 开头的后缀的 lcp

也就是说，对每个询问我们要找到最小的 $p$ 满足 $p>l$ 且 $lcp(l,p)+p>r$

把二叉的后缀树建出来，那么 $lcp(l,p)$ 就转化为树上的 lca，并且所有后缀一定是树上的叶子

把询问离线，挂到 $l$ 对应的叶子上，当询问的 $l$ 变到 sa 序上的下一个时，lca 发生的变化是比较小的，因此我们可以考虑通过一次 dfs 处理询问

有一个 $O(\sum siz)$ 的暴力：我们每次 dfs 到一个点 $u$，假设接下来要进左子树，就把所有右子树的 $h_{lca}+p$ 值加到一个数据结构中，这样我们到叶子时就直接查询这个数据结构中满足条件的即可，而这个数据结构可以用一个下表为 $p$，值为 $h_u+p$ 的线段树来实现

但是这样复杂度可能会很劣，考虑优化。

我们在 dfs 的过程中，会涉及将子树加入数据结构的操作：

• 如果需要加的子树是轻儿子，我们就暴力加，总共会加 $O(n\log n)$ 次，复杂度 $O(n\log^2n)$
• 否则我们启发式合并得到子树内的所有 $p$ 值的 set，然后由于对这棵子树，$h_{lca}$ 是固定的，因此我们可以直接在这个 set 上查出最小的符合条件的 $p$，而这样的情况只会在我们进轻子树时发生，因此对每个叶子只用查 $O(\log n)$ 次，复杂度是 $O(n\log^2n)$ 的，启发式合并也是 $O(n\log^2n)$ 的

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

---

9. WC2016 - 论战捆竹竿 [Keter] ✔️

题面

有足够多个竹竿，每个竹竿上都写着一个同样长为 $n$ 的字符串 $s$

你有一个字符串 $t$，初始为空，你需要进行非零次以下操作：

• 在 $t$ 的末尾插入不超过 $n$ 个任意字符，使得这步操作后 $t$ 的末尾 $n$ 个字符组成的字符串是 $s$

求在 $|t|\le w$ 的情况下，你能产生多少种 $t$ 的长度

$T$ 组数据。

$1\le T\le5,1\le n\le5\times10^5,1\le w\le10^{18}$

题解

Sol

问题相当于初始 $|t|=n$，每次我们可以选择一个 $s$ 的 border $x$，然后 $|t|\leftarrow|t|+x$，问能得到多少 $\le w$ 的 $|t|$

$w\leftarrow w-n$，现在初始 $|t|=0$。

这是一个经典的问题，可以用同余最短路解决，具体地，假设我们可以选择 $+a_1,+a_2,\cdots,+a_n$ 中的操作，那么我们任选一个 $+a_i$，然后通过最短路计算出来，对每个 $0\le k<a_i$，能凑出来的最小的 $\equiv k\pmod{a_i}$ 的数

但是这样复杂度是 $O(n^2)$ 的。

考虑优化，有一个性质：长为 $n$ 字符串的 border 长度可以表示为 $O(\log n)$ 个值域不交的等差数列，这启示我们将一个等差数列放在一起处理

假设当前等差数列为 $a,a+d,a+2d,\cdots,a+rd$，通过直觉，我们感受到在 $\bmod a$ 意义下进行会比较舒服，因此我们考虑如何解决 $\bmod a$ 下的问题

那么我们每次相当于可以 $+d,+2d,+\cdots,+rd$，但由于建出来的边都是转圈的，所以不是很好做

观察到一件事情，对于 $dis$ 最小的点，跨过它的转移一定不优，因为我们可以直接将其转变为从最小点出发的转移

那么可以将这个圈从 $dis$ 最小的点处断开，而剩下的部分我们就可以用单调队列处理了

但是还有一个问题：不同等差数列的模数是不同的，我们需要一种能够切换模数的方法

假设现在是 $\bmod a_0$ 意义下，我们需要切换到 $\bmod a_1$ 意义下

设 $f_i$ 表示 $\bmod a_0$ 意义下 $i$ 的最短路，$g_i$ 表示 $\bmod a_1$ 意义下 $i$ 的最短路

由于有 $+a_1$ 的操作，所以我们仍然只需要求出来能够访问的最小的 $\equiv k\pmod{a_1}$ 的数即可

$f_i$ 的意义是 $f_i+ka_0$ 均可访问，那么我们可以将 $g_{f_i\bmod a_1}$ 先用 $f_i$ 更新，然后对于每个 $i$，从 $g_i$ 向 $g_{(i+a_0)\bmod a_1}$ 转移，这样仍然可以从最小点处断开，重复一边上面的过程就可以做到换模数了

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

---

10. CF1864H - Asterism Stream [Keter] ⭐

题面

你有一个数 $x$，初始为 $1$，每一步操作你有 $\frac12$ 的概率 $x\leftarrow x+1$，另 $\frac12$ 的概率 $x\leftarrow2x$

$t$ 次询问，每次给定 $n$，求 $x\ge n$ 的期望操作次数，对 $998244353$ 取模

$1\le t\le100,1\le n\le10^{18}$

题解

Sol

在讨论区看到一个有趣的做法，遂写。

首先将操作反过来，定义 $f(i)$ 表示 $x>n$ 的期望操作次数，那么有递推式：

$$f(n)=1+\frac12\left(f(n-1)+f\left(\left\lfloor\frac n2\right\rfloor\right)\right)$$

但是这个我们不太会搞。

然后伟大的 amiya 先生说，你的矩阵里存 $[f(n),f(\lfloor n/2\rfloor),f(\lfloor n/4\rfloor),\cdots,1]$，就可以转移了

具体地，$n\rightarrow n+1$ 的转移只和 $n$ 二进制表示中末尾 1 的个数有关系，用 $M_{ct1(n)}$ 表示

我们可以用 $O(\log^4n)$ 的时间，对每个 $k$，预处理出 $\prod_{i=0}^{2^k-2}M_{ct1(i)}$，由此便可以在 $O(\log^3n)$ 的时间内处理每个询问

那么最后的复杂度就为 $O(\log^4n+t\log^3n)$

---

11. 六省联考 2017 - 相逢是问候 [Euclid]

题面

给定长为 $n$ 的数组 $a_1,a_2,\cdots,a_n$，以及常数 $c,p$，你需要维护 $m$ 次操作，每次操作为以下两种中的一种：

• 0 l r，对所有 $i\in[l,r]$ 执行 $a_i\leftarrow c^{a_i}$
• 1 l r，求 $\sum_{i=l}^ra_i\bmod p$

$1\le n,m\le5\times10^4,1\le p\le10^8,0<c<p,0\le a_i<p$

题解

Sol

根据扩展欧拉定理，一个数叠 $O(\log p)$ 层次方塔后结果就不会变了，因此对于每个数只会有 $O(\log p)$ 次变化

那么我们用一棵线段树来维护，每次对区间内仍变化的位置暴力修改

而每次修改需要求一遍次方塔，这可以用扩展欧拉定理解决，复杂度 $O(\log^2p)$，加上分块快速幂就是 $O(\log p)$

那么总复杂度 $O(m\log^2p)$

---

12. 湖北省选模拟 2023 - 棋圣 [Euclid]

题面

给定一个 $n$ 个点 $m$ 条边的简单无向连通图，边有边权，初始有 $k$ 个节点上分别有一个棋子，这些棋子可能是黑子或白子，颜色和棋子位置由输入给定

你可以进行若干次（可以为零）以下操作：

选择任意一个没有棋子的点 $u$，然后对每个棋子，设其在节点 $v$，你需要选择一条 $v\rightarrow u$ 的简单路径，然后让这个棋子沿这条路径走一步（一个节点可能）

最后对于每一对有边直接相连的黑白棋子，你会获得这条边边权的收益

求最大收益

$3\le n\le100,n-1\le m\le\frac12n(n-1),1\le k\le n-1$，边权 $\le10^5$

题解

Sol

如果这张图有一个不为链的生成树，这显然是一个二分图，那么我们可以将所有点在度数 $\ge3$ 的点上反复摩擦，一定将可以将所有在这棵树左部点上的棋子聚到一起，右部点上的棋子聚到一起

对于二分图，我们可以将这些点运送到边权最大的边两端，这样一定是最优的

如果不是二分图，我们可以用奇环来让黑点都在左部点，白点都在右部点，这样再运送到边权最大的边两端

但我们还需要考虑链的情况。

注意到链是二分图，并且棋子的相对顺序不会改变，并且相邻棋子之间的距离不增，那么我们可以进行一个 dp，令 $f_{i,l,r}$ 表示链的前 $i$ 个位置，第 $i$ 个位置上有 $[l,r]$ 的棋子，转移 $O(n)$

最后的复杂度就是 $O(n^4)$

---

13. 湖北省选模拟 2023 - 环山危路 [Keter]

题面

$n$ 个点的竞赛图，$m$ 次询问，每次询问形如：

给定 $t,k,s_1,s_2,\cdots,s_k$，求以 $s_1,s_2,\cdots,s_k$ 为源点，$t$ 为汇点，所有边容量都为 $1$ 的最大流

$1\le n\le3000,1\le m,\sum k\le30000$

题解

Sol

一般最大流的模型不是很好考虑，因此我们转成最小割

设最后源点所处连通块为 $S$，汇点所处连通块为 $T$，那么由于任意两个点之间都有边，最小割的边数可以表示为 $\sum_{u\in T}in_u-\frac12|T|(|T|-1)$

也就是说，当 $|T|$ 一定时，$\sum_{u\in T}in_u$ 越小越好

那么每次询问，我们按 $in$ 排序，贪心扫一遍对每个 $|T|$ 求出最小的 $\sum_{u\in T}in_u$ 即可

复杂度 $O(n^2+nm)$

---

14. 湖北省选模拟 2023 - 山路长环 [Safe]

题面

按如下方式定义 $F(w_1,w_2,\cdots,w_k)$：

两个人在一个长为 $k$ 的环上玩游戏，第 $i$ 条边边权为 $w_i$，有一个棋子一开始在某个节点上，两个人轮流移动棋子，每一步可以将棋子移到其某个相邻点，然后将经过边的边权减少任意正整数，但需要保证边权始终非负

无法操作者输，$F(w_1,w_2,\cdots,w_k)$ 的值为有多少棋子初始位置使得先手必胜

给定长为 $n$ 的数列 $a_1,a_2,\cdots,a_n$，$q$ 次操作，每次操作为以下两种中的一种：

• 1 x y，执行 $a_x\leftarrow y$
• 2 l r，输出 $F(a_l,a_{l+1},\cdots,a_r)$

$1\le n,q\le3\times10^5,0\le y,a_i\le10^6$

题解

Sol

考虑当 $w_1,w_2,\cdots,w_k$ 确定时，如何判断某个特定起点是否合法

观察到一件事情，如果当前棋子相邻的两条出边有一条边权为 $0$，则棋子下一步一定把另一条出边的边权变为 $0$，否则对手下一步可以让棋子再走回来，并将这条出边的边权变为 $0$

分情况讨论，首先是有边权为 $0$ 的情况，这种情况我们可以从边权为 $0$ 的位置拆开，转化成链上的问题

如果当前棋子位置的两边，有一边有奇数条边，那么先手直接走过去并把边权变为 $0$，就能保证获胜

而两边都是偶数条边的情况，后手可以采取类似的策略取得胜利

因此获胜的点数只和非零连续段的长度有关

考虑没有边权为 $0$ 的情况，如果 $k$ 是奇数，那么先手直接把一条边边权取成 $0$ 一定必胜

如果 $k$ 是偶数，那么谁先取出一条 $0$ 边谁输，这意味着两个人都不能走边权为 $1$ 的边，而这和我们直接把原问题的所有边权 $-1$ 没有任何区别，所以我们可以将边权不断 $-1$，直到有边权为 $0$ 的边为止，也就是我们只关心不为最小值的连续段的长度

这些信息是容易放到线段树上维护的，复杂度 $O(n\log n)$

---