AC. 梦想

frank_c1

[CQOI 2017] 小Q的表格

发布于2017年05月03日 | 暂无评论 | 498阅读 | 数论,莫比乌斯反演

题意简述

有一个表格,表格有无穷多行,无穷多列,行和列都从1开始标号。

表格里面每个格子都填了一个整数,第a行第b列的整数记为f(a,b)

这个表格要满足一些条件:

1. 对任意的正整数a,b,都要满足f(a,b)=f(b,a)

2. 对任意的正整数a,b,都要满足b \times f(a,a+b)=(a+b) \times f(a,b)

一开始表格里面的数很有规律,第a行第b列的数恰好等于ab

小Q需要不断的修改表格里面的数,每当修改了一个格子的数之后,为了让表格继续满足上述两个条件,小Q还需要把这次修改能够波及到的全部格子里都改为恰当的数。由于某种神奇的力量驱使,已经确保了每一轮修改之后所有格子里的数仍然都是整数。

小Q还需要随时获取前k行前k列这个有限区域内所有数的和是多少,答案可能比较大,只需要算出答案模10 ^ 9 + 7的值。

1 \le m \le 10 ^ 4, 1 \le a, b, k \le 4 \times 10 ^ 6, 0 \le x \le 10 ^ {18}

算法讨论

观察条件2可以发现所有\gcd相同的格子(i,j)是连通的,即这些格子的整数必定等比例。我们可以设\gcdi的格子的系数是a_i,贡献为F(i)

则答案

Ans = \sum_{i=1} ^ {n} {a_i i ^ 2 F(\lfloor \frac{n} {i} \rfloor)}

对于F(n),有

\begin{aligned} F(n) = & \sum_{i=1} ^ {n} \sum_{j=1} ^ {n} {[\gcd(i,j) = 1]ij} \\ = & \sum_{d=1} ^ {n} {d ^ 2 \mu(d) (\sum_{i=1} ^ {\lfloor \frac{n} {d} \rfloor} {i}) ^ 2} \end{aligned}

如果我们每次分段计算Ans,复杂度是O(m n),考虑线性预处理F(n)

观察F(n)的差分

\begin{aligned} F(n) - F(n-1) = & \sum_{d | n} {d ^ 2 \mu(d) (S ^ 2(\frac{n} {d}) - S ^ 2(\frac{n} {d}- 1)) } \\ = & \sum_{d | n} {d ^ 2 \mu(d) (S(\frac{n} {d}) + S( \frac{n} {d} - 1))(S(\frac{n} {d}) - S(\frac{n} {d} - 1))} \\ = & \sum_{d | n} {d ^ 2 \mu(d) (2 S(\frac{n} {d}) - \frac{n} {d} ) \frac{n} {d}} \\ = & \sum_{d|n} {d ^ 2 \mu(d)(\frac{n} {d}) ^ 3} \\ = & n ^ 2 \sum_{d|n} {\mu(d) \frac{n}{d}} \\ = & n ^ 2 \phi(n) \end{aligned}

于是线性筛预处理\phi(n)再递推一遍即可。

现在的瓶颈是修改和查询a_i。如果树状数组上修改和查询总复杂度是O(m \sqrt{n} \log n),无法通过。不妨平衡一下修改和查询的复杂度,将数列分块,把修改和查询变成O(\sqrt{n}) - O(1)的,则总复杂度就降低到O(m \sqrt{n})啦。