随机浏览
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)$。