随机浏览

idea by GeZhiyuan, solution by GeZhiyuan, shr, std by shr, data by GeZhiyuan

算法 I

考虑必定是存在一些页面，如果到达了这些页面，就回到页面 $1$。可以直接枚举会回到 $1$ 的页面集合 $S$，然后暴力进行高斯消元，复杂度 $O(2^n \times n^3)$，预计通过 $12$ 分。

算法 II

考虑假设 $m$ 轮后，即使没有到达 $n$ 也不会继续操作，只要 $m$ 取到足够大误差就可以接受，复杂度 $O(m \times n^2)$。预计通过 $48$ 分。

通过精细卡常可能能通过 $72$ 分。

算法 III

考虑先强制让所有页面都不会按红色按钮，然后记 $f_i$ 表示目前在页面 $i$，要到页面 $n$ 期望要随机选择几次。每次找出最大的 $f_i$，如果最大的 $f_i$ 不为 $f_1$，则令到达这个页面后会点击红色按钮回到 $f_1$，每次消元复杂度 $O(n^3)$，又至多只会 $n$ 次让页面点击红色按钮，因此复杂度 $O(n^4)$。预计通过 $72$ 分。

算法 IV

考虑利用动态高斯消元优化 算法 III，复杂度 $O(n^3)$。预计通过 $100$ 分。

动态高斯消元的方法可以参考 [集训队互测2015] 最大异或和 的题解。

数字生命

idea by dead_X, solution, std by zhoukangyang, data by zhoukangyang, Rainbow_sjy

小故事

这题是三年前 dead_X 看错一道题后给我报的题意。听完题后我很快就想出了做法！而且感觉这个做法很趣味！之前没怎么见到过这种思路！

后来又在其他题/博客里面发现了这类做法，感觉有点错！但查询了一些选手的看法，他们认为即使见过这些也不简单！

WC2025 中我自己又讲了相关的内容，就当是抹平技术差距了（雾）

算法一

首先，我们差分 $a$ 序列，设差分结果为 $c$。

一次操作就是将 $c$ 的第 $p$ 个位置 $-1$（需要保证 $c_p\ge 1$），将 $c$ 的第 $p+len$ 个位置 $+1$。

此时我们可以将问题看成是，第 $i$ 个位置有 $c_i$（$c_i$ 可以为负） 个石子。每次我们可以将一个石子向前移动 $len$ 步，最终我们要让每个位置的石子数清零。我们可以把这里的 "正 $c_i$" 看成一个石子移动的起点，一个 "负 $c_i$" 看成一个石子移动的终点。

容易发现，起点个数等于终点个数，且如果想要有解，则最多只会有 $m$ 个起点。

根据这个转化，我们可以写出 DP：从往后加入起点，记录此时已经匹配的终点和使用的操作。维护这个 DP 大约要 $\mathcal O(4^m)$ 的复杂度。

根据算法的复杂度和减枝程度，可以获得 $30\sim 75$ 分。

算法二

设 $G_{i,j}$ 表示从第 $i$ 个起点走到第 $j$ 个终点，可以使用哪些操作集合来进行操作。我们给每个 "操作集合" 随机赋值，并将其看成一个集合幂级数。

而我们想要求的是 $\sum_{p} \prod_{i} G_{i,p_i}$，其中集合幂级数的乘法是子集卷积。

注意到我们其实并不关心每个排列带的系数是什么，所以我们要求的也可以是 $\sum_{p} sgn(p) \prod_{i} G_{i,p_i}$。

这就是一个对集合幂级数求 det 的问题了。但是如果使用子集卷积，复杂度带的 $m$ 因子会过多。

我们发现我们可以直接使用或卷积。因为如果或卷积中有重的元素了，那么我们使用的操作的子集和一定和原序列的总和对不上，因此只需再对总和做限制即可。

算答案的每个点值需要 $\mathcal O(m^3)$ 的复杂度，总复杂度 $\mathcal O(2^mm^3)$。

人机验证

idea by xyf007, data, std by zhoukangyang, solution by zhoukangyang, EntropyIncreaser

小故事

这是 NOI2023 后的暑假时给出的做法。

当时 xyf007 找我问这个题。我看了一下发现就是求带深度限制的有根树计数，然后思考了一下，发现有些困难。感觉这是典题，所以咨询了 EI，EI 告诉我他也很好奇这题能不能做。

而 xyf007 告诉我这题能做，而且我之前说出过正确做法。我隐约感觉有些印象，就又开始思考这个问题。断断续续想了几天，我终于想出了一个低于平方的做法！而这题之前的做法并不正确。我把这个做法告诉了 EI，EI 提出用特征多项式优化的做法，能做到 $\mathcal O(n\sqrt n\log n)$。

近几天准备这道题的时候，我重新思考了一下这个问题，发现有了快速的多项式复合后又有另一种 $\mathcal O(n\sqrt n\log n)$ 做法，以及【数据删除】。

题解

显然，问题的难点在于求 $n$ 个点深度不超过 $k$ 的有标号有根树个数。

首先容斥，钦定一些元素的深度恰好为 $k+1$，然后把这些点和他们的祖先都标记了（即保留”虚树“上的点）。

真实的树就是在每个”虚树“上的点上长出一颗新的树，所以答案只和虚树上的点数有关。

可以据此写出一个看起来没啥变化的 DP 来统计虚树上的点数：

$$F_0=-x$$

$$F_i=x(\exp(F_{i-1})-1)$$

求出 $F_k$ 即可得到答案。

接下来我们考虑另一种 DP：

设 $dp_{d,r}(x)$，其中 $[x^c]$ 表示离叶子高度为 $d$ 的恰好有 $r$ 个点，且总点数恰好为 $c$ 的方案数。其中，有 $r \le \lfloor \frac{n}{d} \rfloor$。

从 $dp_{i-1}$ 到 $dp_i$ 的转移系数是个第二类斯特林数。我们要求的是 $dp_{k+1}$。

注意到 $dp_{d,r} = \frac{F_d^r}{r!}$。所以我们可以定一个阈值 $B$，用第一种 DP 算出 $dp_{B}$。

此时考虑如何用 $dp_{B}$ 获得 $dp_{2B}$。这里设 $m = \lfloor \frac{n}{B} \rfloor$

注意到第二维大小不大，因此可以考虑矩阵快速幂。如果直接使用矩阵快速幂，需要对一个 $len$ 维护 $m \times m$ 的矩阵 $G$，其中 $[x^c] G_{i,j}$ 表示第 $0$ 层有 $i$ 个点，第 $len$ 层有 $j$ 个点，总共有 $c$ 个点的有标号有根树个数。

接下来有两种做法。

做法1

把整个矩阵记下来很浪费。考虑设 $H_i(x) = \sum_j G_{i,j}y^j$，可以发现 $H_{i} = H_1^i$。因此只需记录 $H_1$。

接下来考虑如何"翻倍"，即 $len\to len\times 2$。这无非计算 $\sum_i [y^i]H_i H^i$，对 $x$ 这一维插值，对 $y$ 这一维就是多项式复合。

使用 $\texttt {2log}$ 的多项式复合，我们可以做到 $\mathcal O(m^2len\log^2 n)$ 计算长度为 $len$ 的转移矩阵。而对于一个多项式 $F_x$，我们通过其计算 $F_{x+len}$ 可以做到 $\mathcal O(nm)$。

因此复杂度是 $\mathcal O(\frac{B}{len}\times nm+m^2len\log^2 n) = \mathcal O(\frac{n^2}{len}+m^2len\log^2 n)$。取 $len=\frac{n}{m\log n}$ 即可得到 $\mathcal O(nm\log n)$ 的复杂度。

$B$ 最初取 $\sqrt n$，总复杂度 $\mathcal O(n\sqrt n\log n)$。

做法2

这个转移矩阵是对角矩阵，有特征多项式 $f(y) = \prod_{i=1}^{m}(y-x^i)$。

由于 $F_i = dp_{i,1}$，序列 $F_i$ 有线性递推 $f$。我们计算出 $F_B,F_{B+1},F_{B+2},...,F_{B+m}$，然后只要计算出 $y^{B}\bmod f(y)$ 即可知道如何用 $F_{B},F_{B+1},...,F_{B+m}$ 线性表示出 $F_{2B}$。

考虑倍增计算 $y^{B}\bmod f(y)$。注意到 $y^k \bmod f(y)$ 在 $x$ 上的多项式次数是 $\mathcal O(km)$ 的，总大小是 $\mathcal O(km^2)$，因此需要的复杂度是 $\sum_{i} \frac{B}{2^i}m^2\log n = \mathcal O(\frac{n^2}{B}\log n)$。你也可以通过对对 $x$ 这一维插值、对 $y$ 这一维取模来计算这个式子。

$B$ 最初取 $\mathcal O(\sqrt n)$，总复杂度 $\mathcal O(n\sqrt n\log n)$。