Solution: [ARC184E] Accumulating Many Times

· · 题解

提供一个不需要 NTT 的解法。

首先前缀和的性质没有差分好，所以我们将 f(i,j) 等价的定义为最小的 k 使得 A_j 做 k 次差分后得到 A_i。

从优化单个 f(i,j) 的角度入手并不很好做。显然本题需要考虑类似于 Hash 一类的东西，如果两个串的 Hash 值相同则一个就可以做差分变成另一个。

发现差分是有周期的，对于任何一个数组 a 都存在一个数 f(a) 使得 a 在做 f(a) 次差分后会变回 a。那么不断差分实际上就是在一个环上转，不同环上的点互相不可达。可以找到每个点 u 在环上的位置 p_u，那么同一个环上，令环长为 m，从 u 到 v 的距离就是 (p_v-p_u)\pmod m。

现在我们需要做两件事，第一是确定环长，第二是为了区分不同的环我们要从每个环上选一个点做代表，这样我们就可以以这个点为参考确定每个点的位置。

首先有一个重要的 trick：现在我们想要求一个数组 F 在 \bmod~2 意义下的 k 阶差分 (1-x)^kF。首先将 k 进行二进制拆分：

(1-x)^kF\equiv F\prod(1+x)^{2^{k_i}}\pmod 2

然后 (1+x)^{2^k}\equiv 1+x^{2^k}\pmod 2，于是后面那 \Omicron(\log k) 个多项式都只有两项，直接暴力乘就没了。

现在先考虑第二个问题。我们可以选取字典序最小的那个数组作为一个环的代表。为了求出每个数组 a 可以到达的字典序最小的数组 a'，我们考虑令 k 从小到大依次决定是否要乘上 (1+x)^{2^k}。令 a_i=1 且 a_{j}=0(j<i)，那么乘上 (1+x)^{2^k} 时第一个会变化的位置就是 a_{i+2^k}，可以由此决定要不要乘。同时这个过程也同时求出了 a 到 a' 的距离 p_a。

从上述过程容易知道第一个问题的答案：环长就是最小的 2^k 使得 i+2^k>m。于是我们就只需要解决形如 \sum_{1\leq i\leq j\leq n}((p_i-p_j)\bmod m) 的问题，容易用树状数组解决。

Code.