退役选手 Challestend 的 CF 杂题题解 II

直角。

因为觉得把所有东西都堆在一篇 Blog 太挤了，于是考虑每十题一篇（

「CF1408F」Two Different

传送门

想象有一个长度为 $n$ 的正整数序列 $a$ 和函数 $f:\mathbb{N_+}\times\mathbb{N_+}\rightarrow\mathbb{N_+}$。每次操作指定两个位置 $u,v$，然后将当前的 $a_u$ 和 $a_v$ 同时替换为 $f(a_u,a_v)$。您需要给出方案，使得对于任意的序列 $a$ 和函数 $f$，$q$ 次操作后整个序列最多只剩下两个不同的正整数。

比如说 $n=3$，一种可能的最终序列是

$$\{f(a_1,a_2),f(a_1,a_2),a_3\}$$

$n=4$

$$\{f(a_1,a_2),f(a_1,a_2),f(a_3,a_4),f(a_3,a_4)\}$$

$n=5$

$$\{A,A,A,A,a_5\}$$

其中 $A=f(f(a_1,a_2),f(a_3,a_4))$。

$1\leqslant n\leqslant 15000$，$0\leqslant q\leqslant 5\times 10^5$。

注意到我们可以在 $2^k$ 次操作内将一个长度恰好为 $2^k$ 的子区间处理成一个数字。

然后我就卡在这里了。因为 $n$ 的二进制表示也许会有 $3$ 个或者更多的 $1$。于是我就在想怎么将 $4$ 个相同的数字和另外 $2$ 个相同的数字合并成六个相同的数字。

然后想不出来去看题解发现大可不必。直接取 $k=\lfloor\log n\rfloor$ 然后将序列的前 $2^k$ 和后 $2^k$ 个数字合并即可。显然这样处理之后整个序列最多只剩下两个不同的正整数。

于是代码实现就没有了。

「CF543D」Road Improvement

传送门

给定一棵 $n$ 个节点的无根树。对于每个节点 $u$，您需要求出，至少需要标记树上的多少条边，才能使得对于树上除 $u$ 以外任意节点 $v$，路径 $u\rightarrow v$ 上最多存在一条边未被标记。

$2\leqslant n\leqslant 2\times 10^5$。

我觉得大力树上 DP 就好了。

代码实现下辈子再说。

「CF1139D」Steps to One

/* 闲扯开始

本来是想按顺序刷的然而看到这道题于是光速跑过来开搞。

记得高中的时候我刚把位置搬到阿潮旁边的那个晚上大吊阿烜就在写这道题。

……欸不对？哦好像的确是不对。那个晚上阿烜写的是一道虚树题。

算了不管了。

闲扯结束 */

传送门

有一个序列 $a$，初始为空。每次操作等概率随机选择一个 $[1,m]$ 上的整数并将其插入至 $a$ 的末尾。每次操作后计算 $a$ 中所有元素的 $\gcd$，若为 $1$ 则结束，否则再进行下一次操作。求最终 $a$ 的长度的数学期望值。模 $10^9+7$。

$1\leqslant m\leqslant 10^5$。

考虑令 $f(N,M)$ 表示 $a$ 的长度恰好为 $N$ 时其中所有元素的 $\gcd$ 恰好为 $M$ 的概率。那么显然

$$\begin{aligned} &f(N,M)\\ =&\frac{1}{m^N}\sum_{1\leqslant i_1,i_2,\cdots,i_N\leqslant m}[(i_1,i_2,\cdots,i_N)=M]\\ =&\frac{1}{m^N}\sum_{1\leqslant i_1,i_2,\cdots,i_N\leqslant\lfloor\frac{m}{M}\rfloor}[(i_1,i_2,\cdots,i_N)=1]\\ =&\frac{1}{m^N}\sum_{1\leqslant i_1,i_2,\cdots,i_N\leqslant\lfloor\frac{m}{M}\rfloor}\sum_{x|i_k}\mu(x)\\ =&\frac{1}{m^N}\sum_{x=1}^{\lfloor\frac{m}{M}\rfloor}\mu(x)\left\lfloor\frac{m}{Mx}\right\rfloor^N \end{aligned}$$

考虑枚举 $a$ 的长度。设第 $N+1$ 次操作后 $a$ 中所有元素的 $\gcd$ 恰好为 $1$，那么发生这种情况的概率是

$$\frac{1}{m}\sum_{M=2}^{m}f(N,M)\phi(M)$$

其中

$$\begin{aligned} &\phi(M)\\ =&\sum_{i=1}^{m}[i\perp M]\\ =&\sum_{i=1}^{m}\sum_{x|i,x|M}\mu(x)\\ =&\sum_{x|M}\mu(x)\left\lfloor\frac{m}{x}\right\rfloor \end{aligned}$$

值得注意的是需要特判一开始就随机到 $1$ 的情况。

然后对 $N$ 求和，我们得到答案为

$$\begin{aligned} &\frac{1}{m}+\frac{1}{m}\sum_{N\geqslant 1}(N+1)\sum_{M=2}^{m}f(N,M)\phi(M)\\ =&\frac{1}{m}+\frac{1}{m}\sum_{N\geqslant 1}(N+1)\sum_{M=2}^{m}\phi(M)\sum_{x=1}^{\lfloor\frac{m}{M}\rfloor}\mu(x)\left(\frac{\left\lfloor\frac{m}{Mx}\right\rfloor}{m}\right)^N\\ =&\frac{1}{m}+\frac{1}{m}\sum_{M=2}^{m}\phi(M)\sum_{x=1}^{\lfloor\frac{m}{M}\rfloor}\mu(x)\sum_{N\geqslant 1}(N+1)\left(\frac{\left\lfloor\frac{m}{Mx}\right\rfloor}{m}\right)^N \end{aligned}$$

我们遇到这样一个子问题

$$\sum_{n\geqslant 1}(n+1)\alpha^n$$

当然这里保证 $|\alpha|\lt 1$。

设其为 $S(\alpha)$，则

$$\begin{aligned} &\alpha^{-1}S(\alpha)\\ =&\sum_{n\geqslant 0}(n+2)\alpha^n\\ =&\sum_{n\geqslant 0}(n+1)\alpha^n+\sum_{n\geqslant 0}\alpha^n\\ =&1+S(\alpha)+\frac{1}{1-\alpha} \end{aligned}$$

可以解得

$$S(\alpha)=\sum_{n\geqslant 1}(n+1)\alpha^n=\frac{\alpha(2-\alpha)}{(1-\alpha)^2}$$

那么答案就可以记作

$$\frac{1}{m}+\frac{1}{m}\sum_{M=2}^{m}\phi(M)\sum_{x=1}^{\lfloor\frac{m}{M}\rfloor}\mu(x)S\left(\frac{\left\lfloor\frac{m}{Mx}\right\rfloor}{m}\right)$$

第一个 $\sum$ 可以 $O(\sqrt{m})$ 枚举，第二个 $\sum$ 直接 $O(m)$ 暴力算。这样时间复杂度 $O(m\sqrt{m})$ 十分健康可以通过。

其实感觉这个东西可以用 NTT 做到 $O(m\log\text{mod}+m\log m)$，但是反正根号可以过就不用专门动用多项式板子了。

好吧其实是因为我已经不会多项式了。

评测记录

「CF1167F」Scalar Queries

// 口胡一时爽，实现火葬场（光速逃

传送门

给定一个长度为 $n$ 的序列 $a$，保证 $a_i$ 两两不同。如下定义 $f(l,r)$：

将 $a_l,a_{l+1},\cdots,a_r$ 取出并从小到大排序。设结果为 $b_1,b_2,\cdots,b_{r-l+1}$。那么

$$f(l,r)=\sum_{i=1}^{r-l+1}i\cdot b_i$$

求

$$\sum_{1\leqslant l\leqslant r\leqslant n}f(l,r)$$

模 $10^9+7$。

$1\leqslant n\leqslant 5\times 10^5$，$1\leqslant a_i\leqslant 10^9$。

考虑将 $a_i$ 从小到大排序，然后分别计算每个 $a_x$ 的贡献。

设对于当前的 $a_x$，设其左侧有 $N$ 个位置的值小于它，从右到左分别为 $l_1,l_2,\cdots,l_N$；类似地，设其右侧有 $M$ 个位置的值小于它，从左到右分别为 $r_1,r_2,\cdots,r_M$。

考虑到，只要选定区间包括 $x$，答案中就会有一个 $a_x$。这部分的贡献为 $x(n-x+1)a_x$。

如果选定区间包括 $l_i$，答案中就会又有一个 $a_x$。注意这里是只考虑 $l_i$ 这一个位置。这部分的贡献为 $l_i(n-x+1)a_x$。

类似地，$r_i$ 对应部分的贡献为 $x(n-r_i+1)a_x$。

求和，我们得到

$$\left[x(n-x+1)+(n-x+1)\sum_{i=1}^{N}l_i+x\sum_{i=1}^{M}(n-r_i+1)\right]a_x$$

使用线段树简单维护即可。总时间复杂度 $(n\log n)$。

代码实现下辈子再说。

「CF1204E」Natasha, Sasha and the Prefix Sums

传送门

构造一个长度为 $n+m$ 的恰好包含 $n$ 个 $1$ 和 $m$ 个 $-1$ 的序列 $a$，然后定义其价值为其 $n+m+1$ 个前缀和（包括空前缀）中的最大值。对所有可能的序列 $a$，计算价值和。对 $998244853$ 取模。

$0\leqslant n,m\leqslant 2000$。

Warning：$998244{\color{red} 8}53$。

Warning：$998244{\color{red} 8}53$。

Warning：$998244{\color{red} 8}53$。

可以类比一下卡特兰数的求法。

令 $F_k$ 表示最大前缀和 $\leqslant k$ 的方案数。那么考虑一个不符合该条件的序列 $a$，记其前缀和为 $s$。取最小的 $i$ 使得 $s_i\gt k$，那么此时有 $s_i=k+1$，即前 $i$ 个元素中 $1$ 比 $-1$ 多恰好 $k+1$ 个。将 $a_1,a_2,\cdots,a_i$ 取相反数我们就得到了一个恰好包含 $n-k-1$ 个 $1$ 和 $m+k+1$ 个 $-1$ 的新序列 $a^\prime$。

相反地，假设我们现在有一个恰好包含 $n-k-1$ 个 $1$ 和 $m+k+1$ 个 $-1$ 的序列 $a^\prime$，记其前缀和为 $s^\prime$。取最小的 $i$ 使得 $s^\prime_i=-k-1$。将 $a^\prime_1,a^\prime_2,\cdots,a^\prime_i$ 取相反数我们就还原出了 $a$。

也就是说上述的 $a$ 和 $a^\prime$ 之间存在一一映射。注意到 $a^\prime$ 一共有 ${n+m\choose n-k-1}$，我们就得到 $F_k={n+m\choose n}-{n+m\choose n-k-1}$。

特别地，$F_n={n+m\choose n}$。

然后令 $G_k=F_k-F_{k-1}$，计算

$$\sum_{i=\max(n-m,0)}^{n}i\cdot G_i$$

即为答案。

$m=0$ 时需要特判直接输出 $n$。

结果我 WA 了三发。

第一发没特判第二发没注意求和下限第三发忘了删调试信息。

评测记录

话说回来，这数据范围还是太小了啊。建议加大力度开到 $10^7$（光速逃

「CF1594E2」Rubik’s Cube Coloring (hard version)

传送门

给定一棵深度为 $k$，即包含 $2^k-1$ 个节点的完美二叉树。有六种颜色：白，黄，绿，蓝，红，橙。每个节点需要染一种颜色，而且：

1. 相邻节点不能同色。
2. 相邻节点不能一白一黄。
3. 相邻节点不能一绿一蓝。
4. 相邻节点不能一红一橙。

有 $n$ 个节点已经染好色了。问给剩下的节点染色的方案数。模 $10^9+7$。

$1\leqslant k\leqslant 60$，$1\leqslant n\leqslant 2000$。

首先考虑两个子问题。

子问题一：如果有一个深度为 $d$ 的子树，其根节点已经确定了颜色，除此之外没有已经确定颜色的节点。那么该子树的染色方案有多少种？

显然为 $4^{2^d-2}$。

子问题二：有一条从深度递增的链，两端点的深度分别为 $L,R$。且这条链上其他节点（不包括两端点）及其子树均没有已经确定颜色的节点。那么这条链的染色方案有多少种？不考虑两端点的子树。

显然这可以通过一个 $O(k^2)$ 的 DP 解决。

于是我们对给定的 $n$ 个节点建立虚树，然后在上面跑 DP 即可。

至于建立虚树时需要求 dfs 序，我们可以利用完美二叉树的性质在 $O(k)$ 的时间复杂度内求出任意节点的 dfs 序。具体方法读者可自行撕烤。

注意到上面的 DP 并没有考虑到两端点的子树。考虑到一个节点在虚树上当且仅当它是给定点或它是两个给定点的 LCA，只有第一种情况时，该节点可能存在未被考虑的子树，手动计算然后加上即可。

还有就是虚树中的叶子节点在原树中的子树也需要手动计算。

总时间复杂度 $O(nk+n\log n)$，后面那个 $\log$ 是排序的。

然而不怎么好写于是就不写了（

建议加大力度把 $n$ 开到 $10^6$（光速逃

「CF1619H」Permutation and Queries

传送门

给定一个长度为 $n$ 的排列 $p$。$m$ 次操作，每次要么交换 $p_x$ 和 $p_y$，要么给定给定 $x$ 求执行 $x\leftarrow p_x$ 连续 $k$ 次后 $x$ 的最终结果。

$1\leqslant n,m\leqslant 10^5$，$1\leqslant k\leqslant n$。

因为太菜不会做于是被迫去看题解。

好吧其实只是一个先猜出复杂度然后再根据复杂度想搞法的题。

一开始一直在想启发式合并启发式分裂，然后线段树分治搞成只有接环或者是只有断环。总而言之就是困在 poly-log 的怪圈里绕不出去了。然后这道题正解是大根号。

令 $B=\sqrt{n}$。处理出 $p$ 的逆排列 $r$，以及另外一个序列 $f$ 表示每个位置沿着 $p$ 指针跳 $B$ 次到达的位置。预处理需要 $O(\sqrt{n})$ 的时间复杂度。

每次修改的时候，假设 $p_x$ 被修改了，那么有且仅有 $x$ 沿着 $r$ 指针跳 $B$ 次以内经过的位置，也就是 $x$ 沿着 $p$ 指针反着跳 $B$ 次以内经过的位置，这些位置的 $f$ 需要修改。也就是说单次修改的时间复杂度这样就是 $O(B)$。

查询的话，显然可以设 $k=l\sqrt{n}+d$，然后跳 $l$ 次 $f$ 再跳 $d$ 次 $p$ 即可。单次查询时间复杂度 $O(\frac{n}{B}+B)$。

综上所述，总时间复杂度 $O(n\sqrt{n}+m\sqrt{n})$。

评测记录

// 什么时候才能变得想杜爷一样强啊 /se

「CF1626D」Martial Arts Tournament

// 火星艺术主题旅游（光速逃

// 好吧其实 martial 的意思是「军事的」然后 tournament 的意思是「锦标赛」

传送门

给定 $n$ 个数 $a_1,a_2,\cdots,a_n$。您需要指定两个数 $x,y$，然后所有小于 $x$ 的数构成集合 $S_1$，所有大于等于 $x$ 且小于 $y$ 的数构成集合 $S_2$，所有大于等于 $y$ 的数构成集合 $S_3$。然后您需要在这三个集合中插入尽可能少的元素，使得三个集合的大小均变为 $2$ 的自然数幂。

您需要找到一组 $x,y$，使得最终需要插入的元素数最少。您只需给出这个插入元素数的最小值。

多组数据。$1\leqslant n\leqslant 2\times 10^5$，$1\leqslant a_i\leqslant n$。$\sum n\leqslant 2\times 10^5$。

记 $c_k$ 表示有多少个数恰好为 $k$。相当于是说把数组 $c$ 分成三个连续段，记这三个连续段的和分别为 $s_1,s_2,s_3$，那么答案就是 $f(s_1)+f(s_2)+f(s_3)$，其中 $f(N)$ 表示大于等于 $N$ 的最小的 $2$ 的自然数幂。

根据题意每个连续段均不能为空，不过因为不需要给出具体方案，所以这个条件可以无视，因为就算最终找到的方案某一段为空，也一定会存在某个三段均不为空的方案，使得这两种方案得出的答案相同。

证明不会。反正是对的。

考虑枚举最右侧连续段的长度，然后枚举最左侧连续段的贡献——也就是说枚举一个 $2$ 的自然数幂 $p$ 然后找到一个尽可能靠右的前缀使得这个前缀的贡献为 $p$，然后要求尽可能靠右是因为这样可以最小化中间连续段的贡献。

两个枚举的时间复杂度分别是 $O(n)$ 和 $O(\log n)$，再加上二分的一个 $\log$，总时间复杂度 $O(n\log^2n)$。

写到这里我突然意识到，如果直接分别枚举两侧连续段的贡献，那么实际上可以做到 $O(\log^4n)$，差不多相当于是线性的。

不过算了。

评测记录

「CF893F」Subtree Minimum Query

传送门

给定一棵 $n$ 个节点的树，以 $r$ 为根，点有点权。$m$ 次操作，每次给定 $u,k$，查询在 $u$ 的子树内且到 $u$ 的距离不超过 $k$ 的所有点中点权的最小值。强制在线。

$1\leqslant n\leqslant 10^5$，$1\leqslant a_i\leqslant 10^9$，$1\leqslant m\leqslant 10^6$。

不知道这道题正解是什么，不过我感觉我的做法非常的奇怪。

首先定义 $f_{u,k}$ 表示在 $u$ 的子树内且到 $u$ 的距离严格小于 $2^k$ 的所有点中点权的最小值，然后将这个东西预处理出来——至于怎么预处理就发挥人类智慧吧只能说我的方法感觉已经乱了。

然后将询问给出的 $k$ 分解成若干个 $2$ 的正整数次幂，这里令

$$k=\sum_{i=1}^{L}2^{x_i}$$

其中 $x_i$ 两两不同。那么我们首先对于在 $u$ 的子树内且到 $u$ 的距离恰好为 $1$ 的每一个点 $v$，计算 $f_{v,x_1}$ 的最小值；然后再对于距离恰好为 $1+2^{x_1}$ 的每一个点 $v$，计算 $f_{v,x_2}$ 的最小值；依此类推。然后将上述 $L$ 个值与 $u$ 自身的点权取最小值即为答案。

关于「距离恰好为某个数」这个限制条件，我们可以考虑对原树求一个类似于 BFS 序的东西，就是说，进行一次 BFS，然后对于每个点，定义其 BFS 为其是第几个入队的。

我们刚刚定义的这个 BFS 有一个十分容易注意到的性质：原树中深度相同的节点一定会组成一个连续段。而且能够想象得出来的是，如果我们在进行 BFS 和 DFS 时，对于每个点，访问它的出边的顺序相同，那么对于 BFS 序序列中的一个深度相同的连续段，这些点的 DFS 序一定也是递增的。

这就意味着我们能够通过二分查找来找到，在这样一个连续段上，哪个区间恰好属于某个点的子树。然后套用数据结构在 BFS 序上维护区间最小值即可。

单次查询的时间复杂度是 $O(\log^2n)$。至于总时间复杂度，虽然还会有一个预处理但是考虑到这道题 $m$ 相对于 $n$ 范围较大，因此总时间复杂度可以认为就是 $O(m\log^2n)$。

然而……调不出来了 :(

这条评测记录 是我的最后一次提交，它十分英勇地杀到了 test 42，然后在那里折戟而亡。让我们记住它的故事 (???)。

「CF1691F」K-Set Tree

传送门

给定一棵 $n$ 个节点的树和正整数 $k$。

定义 $f(r,S)$ 表示以 $r$ 为根时，包含 $S$ 中所有节点的 $T$ 的最小有根子树的大小。

有根子树：若 $u$ 属于该有根子树，则 $u$ 的所有子节点也都属于该有根子树。

试求

$$\sum_{r\in V}\sum_{S\subseteq V,|S|=k}f(r,S)$$

对 $10^9+7$ 取模。

$3\leqslant n\leqslant 2\times 10^5$，$1\leqslant k\leqslant n$。

令 $1$ 号节点为根节点。

首先考虑 $r=1$ 时的情况，此时这个最小有根子树的大小实际上就是 $\mathrm{size}(\mathrm{lca}(S))$。对于每个点 $u$，$\mathrm{size}(\mathrm{lca}(S))=u$ 的方案数为

$${\mathrm{size}(u)\choose k}-\sum_{v\in\mathrm{son}(u)}{\mathrm{size}(v)\choose k}$$

于是

$$\sum_{S\subseteq V,|S|=k}f(1,S)=\sum_{u\in V}\left[{\mathrm{size}(u)\choose k}-\sum_{v\in\mathrm{son}(u)}{\mathrm{size}(v)\choose k}\right]\mathrm{size}(u)$$

考虑某种类似树上 DP 的换根。现在我们需要将根节点从 $f(r)$ 转移到 $r$，会有如下几种情况：

1. $S$ 完全位于 $r$ 的子树内。
2. $S$ 完全位于 $r$ 的子树外。
3. 不是上述两种情况。

情况 1：转移后，$r$ 的子树大小从原来的 $\mathrm{size}(r)$ 变成了 $n$。另一方面，$\mathrm{lca}(S)=r$ 的方案数为

$${\mathrm{size}(r)\choose k}-\sum_{v\in\mathrm{son}(r)}{\mathrm{size}(v)\choose k}$$

从而这部分的贡献为

$$\left[{\mathrm{size}(r)\choose k}-\sum_{v\in\mathrm{son}(r)}{\mathrm{size}(v)\choose k}\right](n-\mathrm{size}(r))$$

情况 2：转移后，$f(r)$ 的子树大小从原来的 $n$ 变成了 $n-\mathrm{size}(r)$。另一方面，$\mathrm{lca}(S)=f(r)$ 的方案数为

$${n-\mathrm{size}(r)\choose k}-{n-\mathrm{size}(f(r))\choose k}-\sum_{v\in\mathrm{son}(f(r)),v\neq r}{\mathrm{size}(v)\choose k}$$

从而这部分的贡献为

$$\left[{n-\mathrm{size}(r)\choose k}-{n-\mathrm{size}(f(r))\choose k}-\sum_{v\in\mathrm{son}(f(r)),v\neq r}{\mathrm{size}(v)\choose k}\right](-\mathrm{size}(r))$$

情况 3：转移前，$\mathrm{lca}(S)=f(r)$，此时 $f(r)$ 的子树大小为 $n$；转移后，$\mathrm{lca}(S)=r$，此时 $r$ 的子树大小同样为 $n$。即这种情况实际上对答案没有贡献。

时间复杂度 $O(n)$。

评测记录

// 好久没写题已经不会调代码力（悲