• 搬题人：
  • A, B：p_b_p_b
  • C：ezoilearner
• 组题人：p_b_p_b
• 题解：p_b_p_b, ezoilearner

大凯的疑惑

题目来源：

• Petrozavodsk Winter 2020. Day 8. Almost Algorithmic Contest, Problem I

QOJ 链接：https://qoj.ac/contest/448/problem/1462

正解不对拍，爆零两行泪。

$$ \begin{aligned} (a+d)^k-a^k=\sum_{i=1}^k {k\choose i}d^ia^{k-i} \end{aligned} $$ 设 $f_i={k\choose i}d^i$ ，列出前后几项：$f_1=kd, f_2=k(k-1)d^2/2,\cdots,f_k=d^k$ 。

不难发现答案的质因子一定都是 $d$ 的质因子，对 $d$ 的每个质因子 $p$ 分别考虑。设 $C(x)=\max\{i\mid p^i|x\}$ ，即 $x$ 里面 $p$ 的次数。

引理：当 $i\le p^{C(k)}$ 时， $C({k\choose i})=C(k)-C(i)$ 。

证明：$C(k-t)=C(t), 1\le t<p^{C(k)}$ 。

因此就有 $C(f_i)=iC(d)+C(k)-C(i), 1\le i\le p^{C(k)}$ 。并且由于 $C(d)\ge 1$ ，所以可以感性理解得到 $C(f_i)$ 大致是递增的，最小值是 $C(f_1)$ 。并且不难证明，如果 $C(f_1)$ 是唯一的最小值，那么答案就是 $p^{C(f_1)}$ 。

如果这个感性理解是正确的，那么答案就是 $kd$ 中 $d$ 的所有质因子，即 $\gcd(d^{\infty},kd)$ 。

事实上这个感性理解的并没有太大问题，只是在 $i$ 特别小的时候需要修一下。当 $p=2,C(d)=1,2|k$ 时，$C(f_2)=C(f_1)=C(kd)$ ，所以答案要多乘一个 $2$ 。

道路重建

题目来源：

• 2021-2022 ICPC Asia Pacific - Yokohama Regional, Problem E
• Moscow Pre-Finals Workshops 2022 Day 4, Problem E

QOJ 链接：https://qoj.ac/contest/912/problem/3798

显然可以先把城市内的最小生成树求出来，只有这上面的边是有用的。进一步，按照边权从小到大的顺序合并连通块时，如果至少一边没有枢纽车站，那么这条边一定会被计入答案，也不需要考虑了。

进行这些预处理之后可以认为 $m=n-1$ 且所有火车站都是枢纽车站。

人脑模拟 kruskal 的过程：

• 在考虑到第一条高铁线路之前，每个城市都在按照相同的顺序合并，只是速度有快有慢。
• 按 $a$ 从小到大考虑每个城市。
  • 不妨假设 $\arg \min a_i=1$ ，且 $b_1<b_2$ 。
  • 显然城市 $1$ 连的边是城市 $2$ 连的边的超集。因此城市 $2$ 目前的每个连通块都会向城市 $1$ 连恰好一条高铁线路。
  • 连接之后，我们发现两个火车站 $i,j$ 连通当且仅当对应编号在城市 $1$ 中连通，而与这两个火车站实际在城市 $1$ 还是城市 $2$ 无关！并且城市 $2$ 里面也不会连接新的动车线路了。
  • 因此接下来可以令 $a_1:=a_2$ ，然后忽略城市 $2$ 继续做。

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

杜杜和DUDU

题目来源：

• Petrozavodsk Winter 2022. Day 6. 2022 ICPC Training Camp powered by Huawei — Day 1, Problem F

QOJ 链接：https://qoj.ac/contest/824/problem/2610

考虑按 $x$ 从小到大扫描线，维护哪些 $(x,y)$ 可达。

当我们扫完 $x\leq K$ 的时候，扫完的点有 $(x_1,y_1),\cdots,(x_q,y_q)$ .

定义 $g_y=\max(x_i|y_i\leq y)$ ,如果 $(x,y)$ 可达但 $x<g_y$ 那么 $(x,y)$ 没必要保留,因为 $(g_y,y)$ 不可达意味着 $(x,y)$ 不能一次到 $(g_y,y)$ ，注意按照定义一定存在 $(g_y,z),z\leq y$ 的点，所以 $(x,y)$ 到 $(g_y,y)$ 是有转移的，进一步这意味着 $(x,y)$ 不能一次转移到一个横坐标超过 $K$ 的点,因为这样的代价一定不少于 $(x,y)$ 到 $(g_y,y)$ 的代价。

我们需要设计的算法已经很明显了，扫的过程中我们维护一个序列 $seq$ , $seq_y=1$ 表示 $(g_y,y)$ 可达，反之不可达。假设我们现在扫完了小于 $K$ 的部分，现在要加入横坐标为 $K$ 的点，假设其中纵坐标最小的点是 $(K,z)$。

考虑可能的操作形式，一种是横坐标扩大到 $K$ ,但纵坐标不变，这种我们对于 $g_y$ 相同部分的 $y(y\geq z)$ 统一处理，按照势能分析这样的次数是 $O(n)$ 级别的，分析类似单调栈。

还有可能横纵坐标都加大，变成 $(K,z)$ ,这种只要对于每种 $g_y$ 维护可达的最大 $(g_y,y)$ .

在执行完上面两种转移后，我们还可能执行横坐标不变，纵坐标加大的操作，用线段树容易维护 $(K,y)$ 最多往上跳到哪。但我们是不是要对上面两种转移得到的 $(K,y)$ 都执行下这种操作呢。想一想，其实只要转移第一种转移每段转移后得到的最大 $y$ （更小的 $y$ 要么不会增加新的可达点，要么新增的和最大的 $y$ 一样）和第二种的 $(K,z)$ 就好了（如果 $(K,z)$ 可达的话）。

但其实因为我们可能会增加新的纵坐标，所以上面的分析不充分。假如我们新增了 $(K,h)$ ，其中 $h$ 是以前没有出现过的纵坐标，找到在已经出现过的纵坐标中 $h$ 的前驱 $p$，如果 $(K,p)$ 可达且 $(K,p)$ 到 $(K,h)$ 的转移合法，那么可以扩展 $(K,h)$ 了。

具体算法看 std 效果更佳哦。