A – Enlarge GCD
大概可以想到，先把所有的数除掉一个 GCD 之后再来计算出现次数最多的素因子。我们用埃筛筛一下每个数的最小素因子，然后暴力除做标记即可。
大概可以想到，先把所有的数除掉一个 GCD 之后再来计算出现次数最多的素因子。我们用埃筛筛一下每个数的最小素因子，然后暴力除做标记即可。
做起来很舒适的一套题。
忘了写题解，但总觉得要写点啥，所以就有了这篇题集。
刚开始看到分治的标签就下定决心用分治做，没一会发现信息非常难利用就弃疗了。考虑用类似于 KMP 的 AC 自动机的方法完成本题。
首先设置\(dp[i]\)为以\(i\)开头向右延伸的答案，那么我们往左的时候可以合并之，并设置\(nxt[i]\)来进行跳跃；由于得到\(nxt\)数组的过程暴力做时间复杂度会 GG，所以我们可以使用类似 AC 自动机的方式用 Map 合并信息：交换\(nxt[i]+1\)位置的 Map 并设置当前位置。最后做 DP 即可。
我们发现只需要保证在任何时候\(0\)的个数都大于等于颜色的数量。直接考虑一个一个塞球，不仅要考虑同质问题，还要考虑具体的颜色排列非常麻烦，不如我们一次性把所有的球都在序列上放好：设置\(dp[i][j]\)为\(i\)个\(0\)、\(j\)种颜色的局面，我们可以这样转移：
\[ dp[i][j] = dp[i – 1][j] + {n – i + (n – j + 1) \times (k – 2) – 1 \choose k – 2 } dp[i][j – 1] (n – j + 1) \]
解释一下：我们固定住该颜色的球的位置为最左能放置的点，然后乘上\(n – j + 1\)进行染色，并给剩余的\(k-2\)个球选位置。
这道题粗看需要 Link Cut Tree，其实不然：如果我们仍然在把节点 \(1\) 作为根节点来处理子树信息、放入线段树，之后的询问我们只需要灵活的分类讨论即可。在实根为 \(root\) 时，\(u, v\) 之间的 \(LCA\) 显然是 \(lca(u, v), lca(root, u), lca(root, v)\) 之间深度最大的那一个。而修改权值和查询权值，只需要讨论两种祖先关系和平行关系即可。
Continue reading →