如何解决根号分治模板题？

· · 休闲·娱乐

考虑如下问题：

有一个长度为 n 的序列 \{a\}（0-index），初始时全为 0。m 次操作：

  1. 1 p x v 将所有满足 i\equiv x\pmod p 的 a_i 加上 v；
  2. 2 p x 求所有满足 i\equiv x\pmod p 的 a_i 的和。

对 998244353 取模。

考虑定期重构 + 根号分治，设时间块长为 B_1，根号分治阈值为 B_2。

对于时间散块内的修改对查询的影响，相当于求解有两条方程的线性同余方程组，直接 exCRT 可以做到 \mathcal O(mB_1\log n)，稍后可以看到如何通过预处理，将这部分优化至单次 \mathcal O(1)。

同时，对于 p>B_2 的询问，只要我们能够在每个时间块结束后维护出数列 a，就能在总计 \mathcal O\left(\dfrac{mn}{B_2}\right) 的时间复杂度内完成这类询问的整块查询。对于 p\le B_2 的询问，就需要在每次重构时维护所有这类询问的整块答案。

现在要考虑的就是如何重构，并且维护我们需要的信息。对于 p>B_2 的修改，直接暴力加到序列上，总计 \mathcal O\left(\dfrac{mn}{B_2}\right)；否则考虑所有 p\le B_2 的修改对序列的影响，可以写成形式幂级数的形式：

\sum_{p=1}^{B_2}\sum_{i=0}^{p-1}\sum_{j\ge 0}b_{p,i}x^{i+pj}=\sum_{p=1}^{B_2}\dfrac{\sum_{i=0}^{p-1}b_{p,i}x^i}{1-x^p}

设分子为 B_p(x)，那么整个求和就等于：

\sum_{p=1}^{B_2}\dfrac{B_p(x)}{1-x^p}=\dfrac{\sum_{p=1}^{B_2}B_p(x)\prod_{q\neq p}(1-x^q)}{\prod_{p=1}^{B_2}(1-x^p)}

可以通过分治乘做到 \mathcal O(B_2^2\log^2n)。

考虑如何预处理出 p 小的询问的答案 c_{p,i}，通过上面的式子，可以看出要求的就是 A 对每个 (x^i-1) 取模的结果，可以直接分治下去取模，更好的做法是利用转置原理，直接把上面的算法转置即可，由于 B_2=o(\sqrt n)，最好是先做一次整体的取模，复杂度 \mathcal O(n\log n+B_2^2\log^2n)。

现在考虑如何优化 exCRT 的复杂度，我们熟知有 \mathcal O(n) - \mathcal O(1) 的 gcd 算法，现在考虑如何做到 \mathcal O(1) exgcd。参考 Half GCD 的思路，设 K=\lceil(\log_2 n)/3\rceil，首先预处理出所有 A,B\le n^{2/3} 的 exgcd 结果 (g,x,y)；再对于所有高位 X,Y\le n^{2/3}，对区间 [X2^K,(X+1)2^K) 和 [Y2^K,(Y+1)2^K) 模拟辗转相除的过程，直到商不唯一或者有区间包含 0 为止，这样得到一个转移矩阵。

查询的时候，如果 A,B\le n^{2/3} 就直接返回预处理的答案，否则应用一次高位 \lfloor A/2^K\rfloor,\lfloor B/2^K\rfloor 对应的转移矩阵，随后一直执行普通的辗转相除法并同时更新矩阵，直到 A,B\le n^{2/3} 为止，随后直接查表并还原系数即可，可以证明中间至多只会进行 2 次辗转相除，因此查询复杂度 \mathcal O(1)。

总复杂度 \mathcal O\left(n^{4/3}\log n+\dfrac{m}{B_1}(n\log n+B_2^2\log^2n)+mB_1+\dfrac{mn}{B_2}\right)，取 B_1=\mathcal O(\sqrt{n\log n})，B_2=\mathcal O\left(\sqrt{\dfrac{n}{\log n}}\right)，有最优复杂度 \mathcal O(n^{4/3}\log n+m\sqrt{n\log n})。

真的有人会写这种东西吗？？

还没卡常，测了一车数据，10^5 最慢大概要跑到 5s 左右。

然后就是 lxl 说这个东西可以把 P14314 做到 \widetilde O(n^{5/3})，有没有懂的，不会。

私、人間じゃないから。