验题人题解：P17769 「LDOI R2」数树术 / Vocaloid
无名之雾
·
·
题解
验题选手，做了快 3 小时才会，还咕了很久才补代码。
solution
值域很小啊，不妨考虑从因数分解入手。
先考虑考虑序列的情况。
对于一个序列 b_1,b_2,\ldots,b_k，令
x_0=1,\qquad x_i=\varphi(x_{i-1}b_i)
我们需要求出 x_k。
\varphi(x)=\prod_{p^e\parallel x}p^{e-1}(p-1)
也就是说，每次求欧拉函数，相当于对于每个不同的质因子 p，删掉一个 p，再乘上一个 p-1。
直接维护每个质因子的指数似乎不太方便，因为删掉一个 p 后，还会产生一些更小的质因子。
考虑寻找一些更好的定义。
定义一个函数 F_p(x)，满足：
F_p(1)=0,\qquad F_p(xy)=F_p(x)+F_p(y)
对于一个质数 q，定义：
F_p(q)=F_p(q-1)+[p=q].
在这种定义下，对于质数 q，把它替换成 q-1，在这些新的坐标中，只有第 q 个坐标会减少 1。
于是：
F_p(\varphi(x))=F_p(x)-[p\mid x]
原本的欧拉函数操作，现在就转化为只需要考虑一个质数是否出现过。
令：
h_p=F_p(x),\qquad w_p(a)=F_p(a)
那么加入一个点权 a 后：
h'_p=h_p+w_p(a)-[p\mid xa]
这时每个坐标的变化只可能是 w_p(a)-1 或 w_p(a)。
我们记 d_p(a)=w_p(a)-1。
那么无论如何，一次操作至少会让 h_p 增加 d_p(a)。
现在的问题就是如何快速判断 p\mid xa。
我们发现，虽然答案可能很大，但是中间结果出现的质因子其实是有限的。
令 A=\max a_i，考虑集合：
\mathcal P=\bigcup_{1\le a\le A}\operatorname{Prime}(\varphi(a))
其中 \operatorname{Prime}(x) 表示 x 的所有不同质因子。
而：
\varphi(ax)=\varphi(a)\cdot x
\prod_{\substack{p\mid x\\p\nmid a}}\frac{p-1}{p}
如果 x 的所有质因子都属于 \mathcal P，那么 \varphi(ax) 的所有质因子也属于 \mathcal P。
这是因为对于 p\in\mathcal P，p-1=\varphi(p) 的质因子也都属于 \mathcal P。
所以我们只需要维护集合 \mathcal P 中的质数即可。
由于 A\le1000，预处理可以发现：
|\mathcal P|\le50.
也就是说，每个状态实际上就是一个至多 50 维的数组。
不过还有一个问题，我们维护的是 F_p(x)，并不是普通的质因子指数。
设 e_p=v_p(x)。
根据前面定义的变换，可以推出：
e_p=h_p-\sum_{q\in\mathcal P}v_p(q-1)h_q
所以我们可以在 O(|\mathcal P|+R) 的时间内，从所有 h_p 还原出普通质因子指数，其中 R 是所有非零的 v_p(q-1) 的数量。
这样我们就可以判断 p\mid xa，从而在 O(|\mathcal P|+R) 的时间内模拟一次欧拉函数转移。
我们再观察一下欧拉函数的性质。
一个质数 q 被替换成 q-1 后，只会产生比 q 小的质因子。
所以我们可以建立一张有向图：
q\to p\iff p\mid q-1
因为一定有 p<q，所以这是一张 DAG。
令 H 表示这张 DAG 的最长路径边数，显然 H\le 5。
这其实是本题最关键的性质。
它说明一个质因子经过欧拉函数操作后，所产生的影响沿着质数依赖关系不断向更小的质数传递，而依赖链的长度是非常短的。
重新考虑序列 b_1,b_2,\ldots,b_k。
令 h_{p,i} 表示处理完前 i 个数后，答案的第 p 个坐标。
再定义 g_{p,i}，表示只取序列末尾至多 H+1 个数：
b_{\max(1,i-H)},\ldots,b_i
从初始值 1 开始计算，得到的答案的第 p 个坐标。
那么有一个非常重要的结论：
h_{p,i}=
\max\left(
h_{p,i-1}+d_p(b_i),\ g_{p,i}
\right)
也就是说，我们完全不用再考虑之前那个质数是否出现过了，只需要知道上一个坐标，以及末尾一个长度至多为 H+1 的窗口。
我们考虑把同一段后缀，分别从两个不同的初始状态开始计算。
设得到的结果分别为 X,Y，其中 Y\mid X。由于欧拉函数保持整除关系，整个过程中始终有这个性质。
考虑商 X/Y。
因为 F_p 是完全可加的，所以：
F_p(X)-F_p(Y)=F_p(X/Y)\ge0.
假设我们发现第 p 个坐标还有差异，但 X/Y 中已经没有质因子 p。
那么这部分差异一定是由某个更大的质数 q 贡献的，并且可以沿着
q\to\cdots\to p
这条依赖链追溯。
如果经过一次欧拉函数操作后，这种差异仍然没有转化成实际的质因子 p，同时较小的初始状态也没有贡献 p，我们就必须继续向前追溯到一个更大的质数。
不断这样追溯，就会得到一条越来越长的质数依赖链。
但依赖链最多只有 H 条边。
因此，在连续处理了 H 个数之后，如果较大的结果中没有质因子 p，那么两个结果在第 p 个坐标上的值必然相同。
有了这个性质，来看第 i 次转移。
如果 p\mid x_{i-1}b_i，那么这次一定会减去 1，所以：
h_{p,i}=h_{p,i-1}+d_p(b_i)
而且完整序列的结果是对应后缀结果的倍数，因此这个值不会小于 g_{p,i}。
如果 p\nmid x_{i-1}b_i，那么前面 H 步已经足够消除第 p 个坐标上可能残留的额外影响。
此时完整序列和末尾窗口在这个坐标上的结果相同：
h_{p,i}=g_{p,i}
又因为每次转移最多减去 1，此时有
h_{p,i}\ge h_{p,i-1}+d_p(b_i)
于是两种情况合起来，就得到了：
h_{p,i}=
\max(h_{p,i-1}+d_p(b_i),g_{p,i})
特别注意，这并不是说只需要末尾 6 个点就能确定答案。前面所有点的贡献仍然保留在 h_{p,i-1} 中。
我们发现，对于每个质数 p，转移已经完全独立了。
把下标 p 省略，转移就是：
h_i=\max(h_{i-1}+d_i,g_i)
展开一下：
\begin{aligned}
h_1&=\max(h_0+d_1,g_1),\\
h_2&=\max(h_0+d_1+d_2,g_1+d_2,g_2)
\end{aligned}
继续展开，可以发现：
h_k=
\max\left(
h_0+\sum_{i=1}^kd_i,\
\max_{1\le i\le k}
\left(g_i+\sum_{j=i+1}^kd_j\right)
\right)
所以问题就变成了维护一个路径上的前缀和，以及一些经过前缀和调整后的最大值。
这种东西显然就可以考虑树链剖分加线段树了。
我们把树以 1 为根，定义：
S_p(u)=\sum_{x\in1\to u}d_p(a_x)
其中 S_p(0)=0。
由于路径有方向，我们需要分别考虑从上往下走和从下往上走。
对于任意一个节点 u，如果它至少有 H 个祖先，那么我们可以预处理两种长度为 H+1 的窗口。
第一种是从祖先向下走到 u，定义：
D_p(u)=F_p\left(
\operatorname{val}(fa^H(u)\to u)
\right)
这里 \operatorname{val} 表示按题意计算一条有向路径的权值。
假设整个路径最终到达 v，那么这个窗口对答案的贡献就是：
D_p(u)+S_p(v)-S_p(u)
=S_p(v)+\left(D_p(u)-S_p(u)\right)
对于一次询问，S_p(v) 是固定的，所以我们只需要维护：
T^\downarrow_p(u)=D_p(u)-S_p(u)
然后在线段树上查询对应路径的最大值即可。
第二种是从 u 向上走到它的第 H 个祖先，定义：
U_p(u)=F_p\left(
\operatorname{val}(u\to fa^H(u))
\right).
假设当前向上走的这段路径终点是 z，那么这个窗口的贡献为：
U_p(u)+S_p(fa^{H+1}(u))-S_p(fa(z))
同样，对于一次询问，最后的 S_p(fa(z)) 是固定的。
所以我们维护：
T^\uparrow_p(u)=U_p(u)+S_p(fa^{H+1}(u))
这样我们就得到了两棵线段树，一棵维护向上窗口的信息，一棵维护向下窗口的信息。
线段树每个节点维护一个至多 50 维的数组，合并时每个坐标分别取最大值就行。
而且这两个线段树都是静态的，不需要考虑修改。
对于询问 u\to v，令：
z=\operatorname{lca}(u,v).
我们把路径拆成：
u\to z,\qquad z\to v.
首先考虑 u\to z。
我们直接暴力计算前 H 个点的状态。
之后所有新产生的长度为 H+1 的窗口，都是从下往上走的，可以使用 T^\uparrow 进行路径最大值查询。
配合前缀和，就可以一次性计算出走到 z 时的所有坐标。
接下来考虑 z\to v，注意这里不再重复处理 z。
我们再暴力模拟前 H 个点。
这样做是为了处理所有可能跨过 LCA 的窗口。
处理完以后，剩余的窗口都只会从上往下走，可以直接使用 T^\downarrow 进行路径最大值查询。
于是，我们就得到了整条路径最终的 h_p。
最后还原出普通的质因子指数：
e_p=h_p-\sum_{q\in\mathcal P}v_p(q-1)h_q.
答案就是：
ans=\prod_{p\in\mathcal P}p^{e_p}\bmod998244353
预处理每个质数的二进制幂，最后直接快速幂即可。
如果 \mathcal P 为空，那么所有答案都是 1，直接输出即可。
时间复杂度：O(n\log n+m\log^2n)。