某道站外题题解

WYXkk · 2020-09-11 13:59:48 · 题解

题意：

给定序列 a_1,a_2,\cdots,a_n 以及 m，有 q 个操作，每个操作为如下两者之一：

• 更改 a_x 为 y。

• 给定 l,r，求出下列和式对 311021 取模后的值：

  \sum\limits_{v=1}^m\left(\sum\limits_{i=l}^r\sum\limits_{j=i}^r\sum\limits_{S \subset\{i,i+1,\cdots,j\},S\neq\varnothing}[\gcd\limits_{x\in S}(a_x) = v]\right)^v

  即，求出区间所有子区间的所有非空子集的 \gcd，统计为 i 的有 c_i 个，求出所有 c_i^i 的和对 311021 取模后的值。

保证任意时刻 a_i\le m。

Subtask 2（20 pts）m=2

Subtask 3（20 pts）n\le 10^4,q\le10^3

Subtask 4（30 pts）无特殊限制

如果你不是参加了某场比赛而来看非官方题解的，建议先思考一会再往下翻。

难度个人感觉大约紫。

。

。

。

。

。

。

。

。

题解：

Subtask 1 怎么暴力都行。

下面考虑 Subtask 2。

此时所有 \gcd 不是 1 就是 2，同时符合要求的子集个数（含多算的空集）随便推推式子就能算出是 2^{n+2}-2n-4。

关于这个式子是怎么推的：

\begin{aligned}S&=\sum\limits_{i=1}^n\sum_{j=i}^n2^{j-i+1}\\&=\sum_{i=1}^n\left(2^{n-i+2}-2\right)\\&=2^{n+2}-2n-4\end{aligned}

考虑维护区间所有子区间全 2 子集数之和（即 c_2）。

这是一个常见套路：因为乘法分配律的存在，所以，我们可以在线段树的一个节点上维护四个值：sum，num，lsum，rsum，分别表示这个区间的答案，区间 2 的个数，区间 2 的前缀 2 个数次幂的和，区间 2 的后缀 2 个数次幂的和。

例如，对于 [1,2,2]，有 sum=15（空集也会被错计入答案，最后去掉即可），num=2，lsum=7，rsum=10。

合并区间答案时，不跨越两端的就是两个 sum 之和，跨越两端的直接用 lsum*rsum 算即可。

这样我们就解决了 m=2 的情况。

Subtask 3 我并不知道有什么特殊做法。

上面的部分分已经十分提示正解了。

众所周知，\gcd 是 i 的相当于所有都是 i 的倍数，而且 \gcd 不是比 i 的至少两倍。

那么，我们可以如法炮制，建 100 棵线段树，算出全是 i 的倍数的子集的个数为 d_i，那我们就有 d_i=\sum\limits_{i|j}c_j，再减法算出 c_i 即可。可以证明，这一步是 O(m\log m) 的。这一步貌似叫狄利克雷前缀和。

那么我们就做完了……吗？

我们需要 4（单点信息个数）*4（四倍空间）*1e5（长度）*100（线段树个数）*sizeof(int)=610MB 空间，MLE 了（悲）

然而我们可以发现数组开到 262144=2^{18} 就够了（因为 10^5<131072=2^{17}）。这时我们只需要 4*262144*100*sizeof(int)=400MB 的空间，可以通过。

但是我当时没想到这个做法，而采取了另外一种做法，见下。

要是毒瘤出题人把空间开到 384MB 呢？

这时候我们就可以用到一个奇怪的东西：不动态开点严格两倍空间线段树（我不清楚这个 trick 有没有名字……随便取的）。

考虑下面这个函数：

int id(int l,int r){return l+r+((r-l-1)%2==1);}

我不会但是可以证明，按这样对线段树的节点 [l,r] 标号为 id(l,r)，不会出现节点冲突。

这个 trick 我第一次知道是线段树板子的某篇远古题解里面的。

这样，我们就可以在不额外记录左右儿子下标的前提下构造严格两倍空间的线段树了。空间仅需 4*2*1e5*100*sizeof(int)=305MB。

代码（已经尽可能详细地加了注释）