arc144E

tzc_wk · 2022-12-21 15:18:23 · 题解

挺 trivial 又 OI 化的一个想法，但是没想出来。

首先考虑确定了所有 a_i、如何判断是否所有 1\sim n 的路径的点权和都是一个给定的数 x 的倍数。首先点权转边权和。类比网络流建图中的拆点处理即可，这样问题转化为判断是否所有 1\sim n 的边权和是否都是 x 的倍数。

针对这个问题，我们有如下结论：

对于一张带权 DAG，所有 1\sim n 的路径的边权和都是 x 的倍数，当且仅当我们扣掉到达不了 n 和不能从 1 到达的点后，存在一组序列 \{p_i\}，使得对于任意一条边 (u,v,w)，均有 p_v-p_u\equiv w\pmod{x}。

这个思想最早在 CF241E 中出现。常应用于差分约束。

回到此题来，我们考虑有 -1 的情况，先考虑如何判断 x 是否可能成为答案，显然对于所有权值已经确定的边 (u,v,w)，都要有 p_v\equiv p_u+w\pmod{x}，使用带权并查集维护，遇到环就判一下起点和终点是否势能相等即可。至于求最大的 x，显然我们 check 一个 x 是否合法的时候，等价于 check x 是否是一堆数中所有数的因数，这样你只用对这些数求 \gcd 即可，还是使用可持久化并查集维护。