洛谷 P11626 题解

$\text{[Problem Discription]}$

给定长度为 $n$ 的数组 $A_{1\cdots n}$，求

$$\sum _{a=1}^n\sum _{b=a+1}^n\sum _{c=b+1}^n\sum _{d=c+1}^n\sum _{e=d+1}^n\sum _{f=e+1}^n\sum _{g=f+1}^n\left(\underset{i=1}{\overset{a}{\gcd }}{A}_i+\underset{i=a+1}{\overset{b}{\gcd }}{A}_i+\underset{i=b+1}{\overset{c}{\gcd }}{A}_i+\underset{i=c+1}{\overset{d}{\gcd }}{A}_i+\underset{i=d+1}{\overset{e}{\gcd }}{A}_i+\underset{i=e+1}{\overset{f}{\gcd }}{A}_i+\underset{i=f+1}{\overset{g}{\gcd }}{A}_i\right)$$

对 $998244353$ 取模的结果。

其中 $\underset{i=l}{\overset{r}{\gcd }}{x}_i$ 表示 $x_l,x_{l+1},\dots ,x_r$ 的最大公约数。

$7\le n\le 1\times 10^5,1\le x_i\le 1\times 10^9$。

$\text{[Analysis]}$

首先，对数据结构比较熟悉的同学应该知道，静态数组求区间最大公约数可以用 ST 表来解决。

事实上，ST 表的本质就是倍增算法。因此，只要是静态数组的问题，基本都可以用 ST 表解决。

只不过，对于求区间和、区间异或和之类的问题，每个数出现次数对最终答案是有影响的，因此 ST 表查询答案的时候也必须用 $O(\log n)$ 的算法（一步一步跳着查询）。而区间最大最小值、区间最大公约数这些问题和每个数出现次数没有关系，可以直接 $O(1)$ 查询。

式子很复杂，也无法用一般的数论方法化简。因此，只能考虑 dp。

设 $\underset{i=1}{\overset{a}{\gcd }}{A}_i$ 为第一段和，$\underset{i=a+1}{\overset{b}{\gcd }}{A}_i$ 为第二段和，以此类推。

记 $f_{k,i}$ 表示只考虑到第 $i$ 个数，求其前 $k$ 段和，且第 $i$ 个数必须划到第 $k$ 段和时所有方案的总和。$g_{k,i}$ 表示只考虑到第 $i$ 个数，求其前 $k$ 段和，且第 $i$ 个数必须划到第 $k$ 段和时可行的区间划分的方案数。

最终答案即为：

$$\sum _{i=7}^n{f}_{7,i}$$

则 $f$ 的转移方程为：

$$f_{k,i}=\sum _{j=1}^{i-1}\left(f_{k-1,j}+g_{k-1,j}\times \underset{x=j+1}{\overset{i}{\gcd }}{A}_x\right)$$

$g$ 的转移方程为：

$$g_{k,i}=\sum _{j=1}^{i-1}{g}_{k-1,j}$$

直接这么转移肯定会超时，考虑优化。显然 $g$ 可以用前缀和优化。

展开 $f$ 的转移方程：

$$f_{k,i}=\sum _{j=1}^{i-1}{f}_{k-1,j}+\sum _{j=1}^{i-1}{g}_{k-1,j}\times \underset{x=j+1}{\overset{i}{\gcd }}{A}_x$$

显然，红色部分也可以用前缀和优化。考虑优化蓝色部分。

固定 $i$，则 $u_j=\underset{x=j+1}{\overset{i}{\gcd }}{A}_x$ 是一个变下限区间求最大公约数。区间右端点为 $i$ 是固定的。因此，$u_j$ 必然是 $A_i$ 的约数，且 $u_j$ 必然是 $u_{j+1}$ 的约数。故 $u_j\le u_{j+1}$。

因此 $u$ 具有单调性，而 $A_i$ 的约数最多为 $\log A_i$ 个，因此 $u$ 至多可以分为 $\log A_i$ 段，每段内 $u$ 值相同。可以用二分法求出区间分界点。

对于 $u$ 值相同的区间，即 $\underset{x=j+1}{\overset{i}{\gcd }}{A}_x$ 相同的区间，$g_{k-1,j}$ 的和可以用前缀和求出。

总的时间复杂度 $O(n{\log }^{2}n)$。

$\text{Code}$

const int N=1e5+100;
const int mod=998244353;struct ST_gcd{int f[22][N],n,_Log[N];void init(int n,int *a){(this->n)=n;_Log[0]=-1;for(int i=1;i<=n;i++){f[0][i]=a[i];_Log[i]=_Log[i>>1]+1;}for(int j=1;j<=20;j++)for(int i=1;i+(1<<j)-1<=n;i++)f[j][i]=gcd(f[j-1][i],f[j-1][i+(1<<(j-1))]);}int query(int l,int r){int s=_Log[r-l+1];return gcd(f[s][l],f[s][r-(1<<s)+1]);}
}st;//ST 表求区间最大公约数的模版int f[10][N],g[10][N],pref[10][N],preg[10][N];
int n,a[N],ans;int Bineary_Search(int left,int right,int i,int val){int l=left,r=right,ans=-1;while (l<=r){int mid=(l+r)>>1;if (st.query(mid,i)==val){ans=mid;r=mid-1;}else l=mid+1;}return ans;
}struct node{int l,r,val;
};
vector<node> idx[N];void calc_g(){for(int k=2;k<=7;k++)for(int i=k;i<=n;i++){g[k][i]=preg[k-1][i-1];preg[k][i]=(preg[k][i-1]+g[k][i])%mod;}
}
void calc_f(){for(int k=2;k<=7;k++)for(int i=k;i<=n;i++){f[k][i]=pref[k-1][i-1];for(node cur:idx[i]){int l=cur.l,r=cur.r,v=cur.val;f[k][i]=(f[k][i]+1ll*v*(((preg[k-1][r-1]-preg[k-1][l-2])%mod+mod)%mod)%mod)%mod;}pref[k][i]=(pref[k][i-1]+f[k][i])%mod;}
}int main(){n=read();for(int i=1;i<=n;i++)a[i]=read();st.init(n,a);for(int i=1;i<=n;i++){for(int r=i,v=0;r>=2;){v=gcd(a[r],v);int l=Bineary_Search(2,r,i,v);idx[i].push_back((node){l,r,v});r=l-1;}}for(int i=1;i<=n;i++){f[1][i]=gcd(f[1][i-1],a[i]);pref[1][i]=(pref[1][i-1]+f[1][i])%mod;g[1][i]=1;preg[1][i]=i;}calc_g();calc_f();for(int i=7;i<=n;i++)ans=(ans+f[7][i])%mod;printf("%d",ans);return 0;
}