2025/03 & 2025/04 做题记录

$\color{green}\text{P8478 「GLR-R3」清明}$

• 看到乘积先拆成每个最后的台阶选一个上面的水滴。依次考虑初始状态每个台阶水滴去哪里并状压哪些台阶已经选了水滴，可以做到 $O(n^32^k)$。显然我们得找个 $O(\text{poly}(n)2^{n-k})$ 的东西拼起来。注意到只有 $n-k-1$ 个最终台阶的水滴来源不是一个前缀，对它们容斥之后每个台阶的水滴来源都是一个前缀，于是容易设计多项式复杂度的 DP。复杂度 $O(n^32^{n-k})$，拼起来是 $O(n^32^{\frac{n}{2}})$。

$\color{green}\text{CF2045K GCDDCG}$

• 考虑下 $i=1$ 咋求答案。那就是 $\sum_{x \mid \text{gcd}(A)}\sum _{y \mid \text{gcd}(B)} \mu(x) \mu(y)$ 状物对吧。枚举完 $x,y$ 之后答案会和 $x,y,\text{lcm}(x,y)$ 有关，可以快速计算。打个表发现 $\text{lcm}(x,y) \le n$ 的对数只有一千多万对（实际上据题解说好像有重磅结论是 $O(n \log^2n)$ 的），于是对于这些数对暴力计算贡献，然后 $\text{lcm}(x,y)>n$ 的推下式子对于 $x,y$ 分别是独立的两堆东西乘起来，那就好算。对每个 $i$ 跑上面那个算法是 $\sum_i\frac{n}{i}\log^2 \frac{n}{i}$ 即 $O(n \log^3n)$ 的，把不是 square-free 的数对剪枝掉跑得飞快。

$\color{red}\text{P10175 「OICon-02」Subtree Value}$

• 枚举每个 $p^c$ 做，最后合并答案。相当于每个点有个多项式 $(a_i+x)$，记一个连通块的权值为里面所有点多项式的乘积。考虑对每种连通块大小求出该大小的所有连通块的权值之和，然后带入该连通块的大小求值即可。考虑插值求出多项式，注意到 $x^{\underline{pc}} \equiv 0 \pmod {p^c}$，于是这个多项式一定不超过 $(pc-1)$ 次。复杂度 $O(n^2UV)$。

$\color{red}\text{P9157 「GLR-R4」夏至}$

• 设 $F(n,m)=\sum_{i=1}^m f(ni)$，答案为 $\sum_{i=1}^n F(i,m)$。计算 $F(n,m)$，枚举 $n$ 最大质因子 $p^c$ 在 $m$ 侧被选了几次，则 $F(n,m)=\sum_{i \ge 0} \left(F\left(\frac{n}{p^c},\left\lfloor\frac{m}{p^i}\right\rfloor\right)-F\left(\frac{n}{p^{c-1}},\left\lfloor\frac{m}{p^{i+1}}\right\rfloor\right)\right)f(p^{c+i})$。这里有一步小容斥，就是用至少 $i$ 次的贡献减去至少 $(i+1)$ 次的贡献，强制多钦定的那个 $p$ 可以放到 $n$ 那一侧，所以 $c$ 就变成 $(c-1)$。递归边界为 $n=1$，此时 PN 筛计算即可。这里递归的总转移数在本题数据范围下只有 $2 \times 10^7$ 的样子。预处理 $n \times m \le 10^6$ 的 $F(n,m)$ 可以显著优化常数。

$\color{red}\text{P8570 [JRKSJ R6] 牵连的世界}$

• zak 科技。求 $\sum_{i \le n \land j \le m}f(ij)$ 其中 $f(n)$ 为积性函数。如果只算 $\gcd(i,j)=1$ 的 $f(ij)=f(i)f(j)$ 之和，直接莫反容易 $O(n \log\log n)$。考虑枚举 $\gcd$ 为 $d$，设 $h(n)=\frac{f(d^2n)}{f(d^2)}$，则 $h$ 为积性函数，且 $f(ij)=h(i)h(j)f(d^2)$，于是可以用刚刚的做法。总复杂度 $O(n \log n \log \log n)$。本题直接 $f(n)=\sigma_0(n)\varphi(n)$ 就好了。

$\color{red}\text{P6837 [IOI 2020] 数蘑菇}$

• 首先你会一个 $O(\sqrt n)$ 的做法，就是先每次问两个直到得到 $O(\sqrt n)$ 个同色蘑菇（不妨设是 A），然后你问 $\texttt{A,?,A,?,A,?,A}$ 这样的东西就可以每次获取 $O(\sqrt n)$ 个蘑菇里有多少个 A。然后你要卡常。OU 告诉我们，这里有这样一个 trick：考虑取小整数 $k$，初始维护前 $k$ 个蘑菇可能的所有情况（有 $2^k$ 种），每次随机 $K=1000$ 种询问，取最坏情况下情况数减少最多的一种。情况减少后尝试加入接下来的蘑菇，维护总情况数保持在 $O(2^k)$ 级别。

$\color{green}\text{P11927 [PA 2025] 重金属 / Heavy Metal}$

• 想到折半就做完了。启示大概是单起点单终点求路径的形式很适合折半。

$\color{red}\text{CF2048H Kevin and Strange Operation}$

• 重新刻画操作：把所有 $[1,p)$ 的 1 连续段向右延伸一格，然后删除开头。可以不管删除开头这个部分，最后如果操作了 $i$ 次则只保留 $(n-i)$ 位。延伸可以以 1 连续段为单位考虑，也就是选一个前缀的 1 连续段延伸一格。只需对每个 1 连续段被延伸的次数 DP。

$\color{red}\text{P8519 [IOI 2021] 钥匙}$

• 如果从 $u$ 出发最终能到达 $v$ 的话，连一条有向边 $(u,v)$。那么我们所求的答案一定在出度为 $0$ 的 SCC 里。考虑对每个出度为 $0$ 的 SCC 求一个点，如果能求出来的话，从这些点出发暴力遍历的复杂度是对的。怎么求呢，你发现只需维护一个每个点出度至多为 $1$ 的生成森林，每次拉两个的根出来看一下有没有边，连不了之后所有根节点就是我们要的。但是这个太暴力了，我们考虑 Boruvka 的过程，每次从每棵树的根节点出发遍历，以这个树的大小的代价来获得它连向的外面的点或者直接把它标记为无出度 SCC 里的点。这样做一轮树的数量至少减半，于是是 $O((n+m)\log n)$ 的。

$\color{green}\text{CF1687D Cute number}$

• 实际上相当于有一些区间，然后找一个最小的 $x$ 使得 $x+a_i$ 都在区间里。一个显然的观察是答案是 $O(V^2)$ 的。枚举 $a_1+x$ 在哪个区间，然后你注意到此时每个 $a_i$ 最后只能到达至多一个确定的区间，每个 $a_i$ 的贡献是把合法的 $x$ 对某个范围取交。这样暴力做就是 $O(nV)$。考虑优化，刚刚的过程实际上相当于枚举每个 $a_i$，找到一个它对应的区间，考虑改成枚举区间并处理它对应的 $a_i$ 的贡献。注意到如果 $x+a_1$ 所在区间长度为 $l$ 则只会枚举 $O(\frac{V}{l})$ 个区间，所以复杂度为调和级数的 $O(V \log V)$。

$\color{green}\text{[AGC045A] Xor Battle}$

• 倒着做，维护一个集合 $S$ 代表当且仅当走到这里的时候在集合 $S$ 里会使得 $0$ 获胜。发现 $S$ 总是可以被一个线性基表示，做完了。

$\color{red}\text{[AGC044E] Random Pawn}$

• 环没有任何用，可以从最大值断环为链。$b_i=0$ 的问题所有人都会做，见 P5155。有 $b_i$ 的情况，记答案为 $f_i$，就是 $f_i=\max\left(\frac{f_{i-1}+f_{i+1}}{2}-b_i,a_i\right)$，考虑设参数 $c_i$ 使得 $f_i-c_i=\max\left(\frac{(f_{i-1}-c_{i-1})+(f_{i+1}-c_{i+1})}{2},a_i-c_i\right)$，这样就归约到了 $b_i=0$ 的问题。$c_i$ 所有人都会算。

$\color{green}\text{P6222 「P6156 简单题」加强版}$

$\color{green}\text{P7486 「Stoi2031」彩虹}$

$\color{red}\text{Gym103428C Assign or Multiply}$