景点观光

idea, data, solution, std from Ecrade_

引理 1：不移动到子树内没有黑点的结点一定不劣。

我们的目标是遍历到所有黑点，而移动到子树内没有黑点的结点只会徒增操作次数。

引理 2：当移动到结点 $u$ 的子树内时，遍历完 $u$ 子树内的所有黑点再移动到 $u$ 的子树外一定不劣。

若未遍历完 $u$ 子树内的所有黑点就移动到了 $u$ 的子树外，则后面仍需再次移动到 $u$ 子树内遍历剩下的黑点，而这显然只会徒增操作次数。

引理 3：去除子树内没有黑点的结点后得到一棵新树，那么沿着新树的某种欧拉序移动一定不劣。

不妨令红点表示当前未遍历完子树内所有黑点的结点，绿点反之。

根据引理 1，去除子树内没有黑点的结点不会造成任何影响。

根据引理 2，若当前棋子在红点处，则棋子只能往下移动（即移动到深度更大的结点处）。

若当前棋子在绿点 $u$ 处，则考虑离 $u$ 最近且为红点的祖先结点 $r$。

根据引理 2，棋子接下来只能移动到 $r$ 子树内的某个黑点。

观察到在移动的过程中，棋子必然会经过 $r$ 或 $r$ 的某个子结点。

那么在从 $u$ 移动到 $r$ 或 $r$ 的某个子结点的过程中，由于路径上除了 $r$ 为红点，其余均为绿点，故一直往上移动是最优的。

接着，在到达 $r$ 或 $r$ 的某个子结点后，棋子必然又在红点处，这时只能往下移动了。

移动到最后一个黑点后，显然我们一直往上移动至根节点即可。

所以，在整个过程中，我们发现棋子是不会走“回头路”的，其实这也是沿着欧拉序移动的充要条件。

引理 4：沿着新树的欧拉序移动一定是所有移动路径中总路程最短的。

显然，我们必须要经过所有新树的叶结点。

所以，每条边都需要被经过至少两次，而沿着欧拉序移动恰能达到这个理论下界。

注意到总路程 $l$ 为定值（新树边数的两倍），若第二种操作进行了 $x$ 次，则总操作次数为 $x+(l-2x)=l-x$。

所以，我们仅需知道 $x$ 在无限制的情况下的最大值 $x_{\text{max}}$ 即可，这样对于每个询问，答案即为 $l-min(k,x_{\text{max}})$。

考虑使用动态规划计算出 $x$ 取到最大值时的操作次数。

定义 $f_{u,0/1,0/1}$ 表示进入结点 $u$ 的子树内时，棋子处在 $u/u$ 的某个子结点处；遍历完 $u$ 子树内所有黑点后，将要从 $u/u$ 的某个子结点移动到 $u$ 子树外的操作次数。

由于 $f_{u,0,1}$ 和 $f_{u,1,0}$ 的情况是对称的，故我们仅考虑 $f_{u,1,0}$。

对于 $u$ 的所有子结点，我们需找到一个合适的遍历顺序，使得依次拼接后操作次数最少。

容易发现，相邻两个子结点分别是 $0$ 出和 $0$ 进时，则中间只需进行一次操作，而其余情况则需进行两次操作，故一个直观的想法是 $0$ 越多越好。

考虑贪心。

一般情况下，当 $f_{v,0,0}\le f_{v,0,1}$ 时，取 $f_{v,0,0}$ 不劣。

一般情况下，当 $f_{v,0,0}>f_{v,0,1}$ 时，取 $f_{v,0,1}$ 不劣。

$f_{v,0,1}$ 和 $f_{v,1,1}$ 同理。

所以我们得出结论：一般情况下，对于 $f_{v,0,0},f_{v,0,1},f_{v,1,0}$，哪个最小就取哪个，若有多个最小值，则哪个含 $0$ 越多就取哪个。

至于这里的结论为什么只适用于一般情况下，后续会提及。

子结点与子结点之间的拼接情况已处理完，最后仅剩下首尾两处根结点与子结点之间的情况了。

显然，当根结点 $u$ 和子结点 $v$ 分别满足 $1$ 进和 $0$ 进或是 $1$ 出和 $0$ 出，即进/出 $u$ 子树时处在的结点恰为 $v$ 时，便不需要进行操作，而其余情况则需进行一次操作。

仍考虑贪心。

• 当 $u$ 满足 $0$ 进 $0$ 出时：

首尾两处与子结点均需进行一次操作，而中间相邻子结点之间分别满足 $0$ 出和 $0$ 进的数量越多越好。

当没有 $0$ 进 $1$ 出或 $1$ 进 $0$ 出的子结点时，只能将所有 $0$ 进 $0$ 出的子结点紧挨着排，后跟着所有 $1$ 进 $1$ 出的子结点；

否则将一个 $1$ 进 $0$ 出的子结点排在首位，后跟着所有 $0$ 进 $0$ 出的子结点，再跟着 $0$ 进 $1$ 出、 $1$ 进 $0$ 出的交替排列，最后跟着所有 $1$ 进 $1$ 出的子结点。

• 当 $u$ 满足 $1$ 进 $0$ 出时：

将所有 $0$ 进 $0$ 出的子结点紧挨着排，后跟着 $0$ 进 $1$ 出、 $1$ 进 $0$ 出的交替排列，最后跟着所有 $1$ 进 $1$ 出的子结点。

• 当 $u$ 满足 $1$ 进 $1$ 出时：

若 $u$ 仅有一个子结点，暴力考虑所有情况即可；

否则将所有 $0$ 出 $0$ 进的子结点紧挨着排，后跟着 $0$ 出 $1$ 进、 $1$ 出 $0$ 进的交替排列，再后跟着所有 $1$ 出 $1$ 进的子结点，最后跟一个 $1$ 出 $0$ 进的的子结点。

注意这里需要再考虑强制将所有子结点变为 $0$ 进 $0$ 出的子结点的情况，因为这时的贪心可能就不奏效了。注意此时若 $u$ 为黑点则需中途再进行一次操作去遍历 $u$。

至此，我们便用 $O(\sum n+\sum q)$ 时间复杂度解决了本题。

509 号迷宫

idea, data, solution, std from JohnVictor

算法一（暴力）

直接 $\text{DP}$，复杂度 $O(n^2)$，可以通过第一个子任务。

算法二（部分分）

输出 $0$ 可以通过第二个子任务。第三个子任务的答案可以用一些组合数简单表示。对于第四个子任务，可以看做 $O(np)$ 个点加一个下三角，下三角部分的贡献可以简单反射容斥计算，剩下部分暴力即可。第五个子任务留给小常数 $O(n\sqrt{n\log n})$ 的直接分块 $\text{NTT}$ 和大常数正解。

算法三（正解）

下面的分析中，令块长 $B=p$。

考虑平移指数基。具体地，对于每一列，考虑维护一个形如 $P(x)/(1-x{)}^k$ 的多项式表示一整列的 $\text{DP}$ 值构成的生成函数。

我们要支持的操作是加一个单项式，查询一项系数（这两个操作足以解决每一列有一个不能走的点的问题），将 $k$ 加上 $1$（也就是一次前缀和）。

考虑定期重构。我们维护 $P(x)(1-x{)}^k$ 的形式。每一次将 $k$ 减小 $1$，变成了 $0$ 就重构。这样，对于这个形式查询一项系数是 $O(B)$ 的。

利用 $1-x^p=(1-x{)}^p$，重构的时候只用除以 $(1-x^B)$，这个相当于隔 $B$ 个做一次前缀和，复杂度 $O(n)$。

主要的问题是加一个单项式之后再除以 $(1-x)$ 怎么办。这个只用额外维护成 $P(x)(1-x{)}^k+Q(x)/(1-x{)}^k$ 即可。注意这里的系数还是可以 $O(k)$ 来计算的，因为 $Q$ 不超过 $k$ 个非零系数，单个贡献可以 $O(1)$。

所以现在的复杂度为 $\mathcal{O}(np+\frac{n^2}{p})$，可以通过所有子任务。

算法四

考虑每 $p$ 条斜线（即 $i+j=t\times p$ 的位置 $(i,j)$）算一次 dp 值。转移的时候可以考虑对障碍点容斥，钦定一些障碍点被经过了，并对可能产生转移的两个障碍点之间计算贡献。

斜线 -> 斜线的贡献可以 $\mathcal{O}(\frac{n^2}{p})$ 处理；障碍点 -> 障碍点，斜线 -> 障碍点和 障碍点 -> 斜线的贡献均可以 $\mathcal{O}(np)$ 处理。

时间复杂度 $\mathcal{O}(np+\frac{n^2}{p})$。

红场阅兵

idea, data, solution, std from zhoukangyang. sol-114514,-1919810 from bulijiojiodibulido

APIO2024 会讲的。大家可以提前复习一下积性函数相关知识。UPD：apio 讲课的核心内容放在了 这里

算法 -114514,-1919810 是 bulijiojiodibulido 老师验题时用的做法，算法一、算法二是官方题解做法。

算法 -114514

令 $t=gcd(i,j)$，如果我们提取 $i$ 和 $j$ 中与 $t$ 相关的所有因子，即令 $i=t_i{s}_i,j=t_j{s}_j$，其中 $gcd(t_i,s)=gcd(t_j,s)=1$。那么有 $f(ij)=f(s_i)f(s_j)f(t_i{t}_j)$。

所以可以考虑枚举 $t_i,t_j$，满足它们有相同的素因子分布（即 $\text{rad}(t)=\text{rad}(t_i)=\text{rad}(t_j)$，其中 $\text{rad}(n)=\prod _{p|n}p$），然后计算上式。这个时候我们还有 $gcd(s_i,t)=gcd(s_j,t)=1$ 的条件，如果直接反演，那么复杂度比较高。

类似构造系数 $g(y_i,y_j)$，满足 $\sum _{x_i|y_i,x_j|y_j,\text{rad}(x_i)=\text{rad}(x_j)}g(x_i,x_j)=f(x_i{x}_j)$。令 $F(n)=\sum _{i=1}^{n}f(i)$。那么答案为 $$\sum _{t_i,t_j,\text{rad}(t_i)=\text{rad}(t_j)}g(t_i,t_j)F(\lfloor n/t_i\rfloor )F(\lfloor n/t_j\rfloor )$$。因为我们能保证每对 $t_i,t_j$，前面加的总系数为 $f(t_i{t}_j)$。

对于函数 $g$，在上面等式中，右侧是积性，也就是关于每个素因子是独立的，所以 $g$ 的取值也是对于每个素因子都是独立的。所以只需要对于所有素数，预处理出 $g(p^i,p^j)$ 的值（事实上是一个次数为 $2(i+j)$ 的多项式），那么对于任意两个数，可以快速算出上述的 $g$ 值。

这个时候直接枚举 $t_i,t_j$，也就是从小到大枚举每个素数，以及在 $t_i,t_j$ 中的指数就能快速计算答案。枚举代价为 $1$ 到 $n$ 内所有 $\text{rad}$ 相同的数字的对数，好像是 $O(n)$ 级别的，可以通过 $3\times {10}^7$ 的数据。

算法 -1919810

考虑如何加速这个过程，我们希望能快速计算出比较大的素数的贡献。

$d{p}_{n_1,n_2,p}$ 表示从大到小枚举因子到 $p$，$n_1=\lfloor n/t_i\rfloor ,n_2=\lfloor n/t_j\rfloor$，$g$ 的乘积。对于大于 $\sqrt{n}$ 的素数，它一定是从 $(n,n)$ 转移向 $(\lfloor n/p\rfloor ,\lfloor n/p\rfloor )$，并且乘上的是一个四次多项式。

那么我们只需要预处理 $\lfloor n/p\rfloor$ 相同的每段的素数的四次多项式的值，就可以快速完成这些素数的转移。对于剩下的素数，我们枚举它们的指数，从大到小转移即可。

如果使用记忆化，当 $n={10}^9$ 的时候，状态数大概在 $2\times {10}^6$ 级别，转移大概在 $2\times {10}^8$ 级别，使用精细的实现卡常数就可以通过。

实际大部分的状态都是在小素数的地方，所以可能可以从小素数枚举然后 meet in the middle，但是没编出来。

算法一

考虑把积性函数推广至二维，如果函数 $f(x,y)$ 是二维积性函数，假设 $p_i$ 是从小到大第 $i$ 个质数，$x=\prod _i{p}_i^{a_i}$，$y=\prod _i{p}_i^{b_i}$，那么 $f(x,y)=\prod _{i}f(p_i^{a_i},p_i^{b_i})$。容易发现我们要求的是二维积性函数前缀和。

考虑设计积性函数 $g(x,y)$ 满足 $g(p^a,p^b)=f(p^a,1)f(1,p^b)$。对于这个函数，其前缀和 $\sum _{i\le n_1}\sum _{j\le n_2}f(i,1)f(1,j)$ 是相当容易计算的。观察 $h=f/g$。我们发现 $h(p^k,1)=h(1,p^k)=0$。

暴力枚举 $h$ 有值的位置，可以证明复杂度是 $\mathcal{O}(n)$。期望得分 $70$ 分。

算法二

考虑优化之前的算法，设计二维积性函数 $g_3$ 满足 $g_3$ 只在 $g_3(x,x)$ 处有值且值为 $h(x,x)$，接下来令 $h^{\prime }=h/g_3$。

此时有值的 $h^{\prime }(p^a,p^b)$（$p\in \mathbb{P},a,b\ge 0$，$a+b\ne 0$）就满足 $a,b\ge 1$ 且 $a\ne b$ 了。

接下来暴力枚举 $h^{\prime }$ 中的有值元素 $(x,y)$，计算 $\sum _{u\le n/x,v\le n/y}(g\ast g_3)(u,v)$，把这些答案带上系数加起来就能得到最终答案了。

而 $\sum _{i=1}^A\sum _{j=1}^B(g\ast g_3)(u,v)=\sum _{k=1}^{min(A,B)}{g}_3(k,k)\sum _{i=1}^{A/k}\sum _{j=1}^{B/k}g(i,j)$。暴力整出分块计算答案。

我们当然要筛 $f(x,1)$ 和 $g_3(x,x)$ 的块筛前缀和。可以证明，除此之外的复杂度不超过 $\mathcal{O}(n^{2/3}\log n)$。

其实还可以更快一点，不过没必要了。