自动搬运

查看原文

来自洛谷，原作者为

	george0929 ด้้้้้็้้้็็็็็้้้้้็็็็็้้้้้้็็็็็้้้้้็็็็็้้้้้้็็็็็้้้้้็็็็็้้้้้้็็็็็้้้้้็็็็็้　蒟蒻一枚

搬运于2025-08-24 23:08:57，当前版本为作者最后更新于2025-01-26 18:30:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前置知识：ST 表，二分，前缀和优化 DP，最大公约数的性质。

转化一下题意，把序列分成八段，取前七段的 $\gcd$ 的和作为这个方案的贡献，求所有方案的贡献和。

有一个 $O(n^3)$ 的 DP：令 $f_{i,j}$ 表示第 $j$ 段结尾是 $i$ 的贡献和， $g_{i,j}$ 表示第 $j$ 段结尾是 $i$ 的方案数，则 $f_{i,j}\leftarrow \sum\limits_{k=1}^{i-1} (f_{k,j-1}+g_{k,j-1}\times \gcd\limits_{x=k+1}^{i} a_x),g_{i,j}\leftarrow \sum\limits_{k=1}^{i-1} g_{k,j-1}$。

考虑优化，$g$ 显然可以前缀和优化成 $O(n)$。

考虑用前缀和优化 $f$，发现难点在 $\gcd$。

由于右端点固定时，区间 $\gcd$ 至多有 $\log V$ 种取值，所以先用 ST 表预处理区间 $\gcd$，然后对于每个右端点二分计算 $\log V$ 种不同取值的左端点，然后前缀和优化，分 $\log V$ 段转移 $f$ 即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=998244353;
void upd(int &a,int b){
	b=(b%mod+mod)%mod;
	a=(a+b)%mod;
}
int gcd(int a,int b){
	if(b==0) return a;
	return gcd(b,a%b);
}
int n,a[100005];
struct node{
	int l,r,v;
};
vector<node> V[100005];
int st[100005][21];
int f[100005][8],g[100005][8];
int sumf[100005][8],sumg[100005][8];
int cost(int l,int r){
	int k=__lg(r-l+1);
	return gcd(st[l][k],st[r-(1<<k)+1][k]);
}
void workg(int k){
	for(int i=1;i<=n;i++){
		upd(g[i][k],sumg[i-1][k-1]);
		upd(sumg[i][k],sumg[i-1][k]+g[i][k]);
	}
}
void workf(int k){
	for(int i=1;i<=n;i++){
		upd(f[i][k],sumf[i-1][k-1]);
		for(auto cur:V[i]){
			int l=cur.l,r=cur.r,v=cur.v;
			upd(f[i][k],v*(sumg[r-1][k-1]-sumg[l-2][k-1])%mod);
		}
		upd(sumf[i][k],sumf[i-1][k]+f[i][k]);
	}
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		st[i][0]=a[i]; 
	}
	for(int j=1;j<=20;j++){
		for(int i=1;i<=n;i++){
			if(i+(1<<(j-1))>n) continue;
			st[i][j]=gcd(st[i][j-1],st[i+(1<<(j-1))][j-1]);
		}
	}
	for(int i=1;i<=n;i++){
		int r=i,v=a[i];
		while(r>=2){
			v=gcd(v,a[r]);
			int L=2,R=r,l=r;
			while(L<=R){
				int mid=(L+R)/2;
				if(cost(mid,i)!=v){
					L=mid+1;
				}else{
					R=mid-1;
					l=mid;
				}
			}
			V[i].push_back({l,r,v});
			r=l-1;
		}
	}
	for(int i=1;i<=n;i++){
		f[i][1]=gcd(f[i-1][1],a[i]);
		upd(sumf[i][1],sumf[i-1][1]+f[i][1]);
		g[i][1]=1;
		sumg[i][1]=i;
	}
	for(int k=2;k<=7;k++) workg(k);
	for(int k=2;k<=7;k++) workf(k);
	int ans=0;
	for(int i=1;i<=n;i++){
		upd(ans,f[i][7]);
	}
	cout<<ans<<"\n";
	return 0;
}