P16331

· · 题解

tag：数论、exCRT、exGCD、构造、Ad-hoc、*2700

有一个长度为 n 的环，每个点上写有一个数，初始时所有数均为 0。 给定两个长度为 n 的序列 \{a_n\}, \{b_n\}，你可以操作若干次：任取一个位置 1 \le i \le n，将从 i 开始的长度为 i 的子段（下标模意义下）整体加上或减去 b_i。 问是否存在一种操作方式，使得最终环上的每个位置权值恰好为 a_i？如果有请输出每个位置对应的系数序列，如果没有请报告无解。

1 \le n \le 10^6, 0 \le |a_i| \le 10^9, 1 \le b_i, {\color{red}{\text{lcm}(b_i)}} \le 10^9

给两个可能人类一点的做法。

法一

我们考虑差分序列 d_i = a_i - a_{i-1}，特别地对 i = 1 有 d_1 = a_1 - a_n。那么一个操作 i 对差分序列的影响就是在起点处加上 b_i，在终点 + 1 \bmod n 处减去 b_i。那么对任意一个位置 j 满足 d_j = b_j - \sum_{2i \bmod n = j} b_i。

上述约束构成一张 DAG，每条边形如 i \to 2i \bmod n。对于入度为 0 的点此时方程就是 d_i = b_i，否则解出 d_i 之后将其带入到它指向的点就可以消元。

这个拓排结束之后图上只剩下环了，然后对每个环约束就是类似于 b_i \times c_i - b_{i-1} \times c_{i-1} = d_i 这种东西。那么你沿着一个环一直加下去所有 b_i 会抵消掉，最后得到对环 C 的限制 \sum_{u \in C} d_u = 0，这个是有解条件。与此同时，环上每一个位置的操作都必须满足被它所对应的 b 整除，这个是一个同余方程组，可以直接 exCRT 解出，反代回去这个解出来的特解即可让所有位置均为合法整数。可能做的过程中要考虑一些什么先除后乘的东西。

最后我们考虑全局的限制，一次长度 i，大小为 b_i 的操作会给整一个序列带来 i \times b_i 的变化量，所以必须要满足 \sum_{i=1}^{n} a_i = \sum_{i=1}^{n-1}(i \times b_i \times c_i) + n \times c_n \times b_n。非环点的情况已经固定了，只考虑每个环对应的独立偏移量，它的增量的最小步长是 \Delta_{C} = \text{lcm}(b_{C_j}) \times \sum_{u \in C} u。然后 b_n 对应的增量最小步长为 n \times b_n，所以就是一个方程 c_n \times (n \times b_n) + \sum_{C \in G} \text{coef}(C) \times \Delta_{C} = \sum_{i=1}^{n} a_i - \sum_{p\ \text{is fixed in DAG}} c_p \times b_p。这个可以扩展欧几里得求解。解出每个环对应的 \text{coef} 后将最终的偏移量加回每个变量内。

时间复杂度是 \mathcal{O}(n \log V) 的。

法二

不妨直接从每个位置去考虑，对一个位置，可以列出所有位置对他的贡献，也即对 1, 2, 3, \dots, n 中每一个可以影响到 i 的位置，统计他们的贡献，得到 \sum c_j \times b_j = a_i 这样的方程。然后对于相邻的两个方程，可以考虑换一个维度去思考：固定我这个位置对应的 c_i \times b_i，对其余位置做差消掉相同的项，从而得到 c_i 的限制。

此时如果 n 是偶数，下标是奇数那么只剩下我自己一个数，直接解出来了。否则我们考虑奇偶交替消元，这样最后每一行剩下来的只有 \mathcal{O}(1) 个元。

最后我们考虑对第 n 行引入它对应的所有 n 元限制，从而直接用类似于高斯消元的过程解决全局的影响，此时可以进一步引入 \equiv 0 \pmod {b_i} 的限制去用 exCRT 解决整除的影响，最后把解出来的第 n 行的元反代回去，即可解出所有未知数。

时间复杂度同样也是 \mathcal{O}(n \log V) 的。

其实这三个做法本质上都在干一样的事情，只是观察的角度不一样。