G. Summmon （Codeforces 2241）

G. Summmon

题意

给定数组a。对任意一个子数组b，可以执行任意次操作：

选择 1 <= i < m b[i + 1] := b[i + 1] + b[i] 或者 b[i + 1] := b[i + 1] - b[i]

记f(b)为经过若干次操作后，max(b) - min(b)能达到的最小值。

要求计算所有子数组的f之和：

sum f(a[l ... r])

答案可能超过long long。

先看操作本质

第一个元素永远不会被改变，因为没有位置能操作到它。

对于一个子数组：

b = [b1, b2, ..., bm]

设当前要处理第i个数。它前面的数是：

b1, b2, ..., b[i - 1]

通过操作，第i个数可以加上或减去前面这些数凑出来的整数线性组合。根据 gcd 的性质，它最终能变成的数恰好满足：

新值 ≡ 原值 (mod gcd(b1, b2, ..., b[i - 1]))

也就是说：

第 i 个数能怎么调整，只由它前面所有数的 gcd 决定。

这是整道题最重要的观察。

核心结论

考虑一个子数组：

b = [b1, b2, ..., bm]

令：

x = b1

从左往右找第一个不能被x整除的位置p：

b[p] % x != 0

如果不存在这样的p，那么：

f(b) = 0

如果存在这样的p，令：

r = b[p] % x

那么：

f(b) = min(r, x - r)

一句话总结：

一个子数组的贡献，只看首元素和后面第一个不能被首元素整除的数。

为什么只看第一个不整除的位置

还是设x = b1。

情况 1：后面全是 x 的倍数

如果：

b2, b3, ..., bm

全部都是x的倍数，那么可以从左到右把每个元素都调整成x。

例如：

[6, 12, 24] -> [6, 6, 6]

所以此时：

f(b) = 0

情况 2：出现第一个不是 x 倍数的数

设p是第一个满足b[p] % x != 0的位置。

因为p前面的数都是x的倍数，所以在处理b[p]之前，前缀 gcd 仍然是x。

因此b[p]只能变成：

b[p] + k * x

也就是所有和b[p]模x同余的数。

令：

r = b[p] % x

那么b[p]离x最近的可能位置，距离就是：

min(r, x - r)

记这个值为w。

所以答案至少是w。

另一方面，答案确实可以做到w：

• 如果r <= x - r，把b[p]放到x + r，区间可以是[x, x + r]。
• 如果r > x - r，把b[p]放到r，区间可以是[r, x]。

这个区间长度正好是w。

处理完b[p]后，前缀 gcd 会变成：

g = gcd(x, b[p])

因为g同时整除x和b[p]，所以它也整除r和x - r，从而整除w。

于是：

g <= w

长度为w的连续整数区间里，至少能覆盖模g的所有余数。后面的前缀 gcd 只会继续变成g的因子，所以后面的每个元素都可以被调整进这个区间，不会让答案继续变大。

因此：

f(b) = w = min(b[p] % x, x - b[p] % x)

如何统计所有子数组

固定左端点l。

令：

x = a[l]

找到最小的p > l，满足：

a[p] % x != 0

如果不存在这样的p，那么所有以l开头的子数组贡献都是0。

如果存在这样的p，令：

w = min(a[p] % x, x - a[p] % x)

那么：

• 右端点r < p时，子数组a[l ... r]后面全是x的倍数，贡献是0。
• 右端点r >= p时，第一个不整除位置都是p，贡献都是w。

这样的右端点有：

n - p + 1

个。

所以左端点l对总答案的贡献是：

w * (n - p + 1)

怎么快速找到 p

我们需要对每个l找第一个不能被a[l]整除的位置。

考虑区间[l + 1, mid]。

这段区间里的所有数都能被a[l]整除，等价于：

gcd(a[l + 1], ..., a[mid]) % a[l] == 0

所以可以：

1. 建一个 gcd 稀疏表，支持O(1)查询区间 gcd。
2. 对每个左端点l，二分第一个不满足条件的位置p。

为什么可以二分？

如果[l + 1, mid]已经包含了一个不能被a[l]整除的数，那么这段区间的 gcd 也不可能再被a[l]整除。所以条件具有单调性。

例子

数组：

[6, 4, 8]

按左端点统计：

总答案：

4

复杂度

设数组长度为n。

所有测试用例的n之和不超过2 * 10^5，可以通过。

C++ 代码

下面的代码没有依赖__int128或 Boost。答案用一个很小的大整数维护，只需要支持加上一个long long和输出。

#include<bits/stdc++.h>usingnamespacestd;usingint64=longlong;structBigInt{staticconstintBASE=1000000000;vector<int>d;voidadd(longlongx){inti=0;while(x>0){if(i==(int)d.size())d.push_back(0);longlongcur=(longlong)d[i]+x%BASE;d[i]=int(cur%BASE);x=x/BASE+cur/BASE;i++;}}stringstr()const{if(d.empty())return"0";string res=to_string(d.back());for(inti=(int)d.size()-2;i>=0;i--){string part=to_string(d[i]);res+=string(9-part.size(),'0')+part;}returnres;}};intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intT;cin>>T;while(T--){intn;cin>>n;vector<int64>a(n+1);for(inti=1;i<=n;i++){cin>>a[i];}intK=__lg(n)+1;vector<vector<int64>>st(K,vector<int64>(n+1));for(inti=1;i<=n;i++){st[0][i]=a[i];}for(intk=1;k<K;k++){intlen=1<<k;for(inti=1;i+len-1<=n;i++){st[k][i]=gcd(st[k-1][i],st[k-1][i+(len>>1)]);}}autorange_gcd=[&](intl,intr)->int64{intlen=r-l+1;intk=__lg(len);returngcd(st[k][l],st[k][r-(1<<k)+1]);};BigInt ans;for(intl=1;l<=n;l++){if(l==n)continue;int64 x=a[l];intpos=n+1;intlow=l+1;inthigh=n;while(low<=high){intmid=(low+high)/2;int64 g=range_gcd(l+1,mid);if(g%x==0){low=mid+1;}else{pos=mid;high=mid-1;}}if(pos<=n){int64 r=a[pos]%x;int64 w=min(r,x-r);ans.add(w*1LL*(n-pos+1));}}cout<<ans.str()<<'\n';}return0;}

小结

这题最关键的一步是不要模拟操作，而是把操作转成 gcd 和同余：

后面的数只能在某个 gcd 模意义下移动。

再利用首元素固定这一点，可以进一步发现：

每个子数组只由第一个不被首元素整除的位置决定贡献。

于是问题就变成了：

对每个左端点，快速找到第一个不整除的位置。

用 gcd 稀疏表加二分即可完成。