专栏文章

题解：P11626 [迷宫寻路 Round 3] 七连击

HHPXXZYY
P11626题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqclv56
此快照首次捕获于
2025/12/04 02:36
3 个月前
此快照最后确认于
2025/12/04 02:36
3 个月前
查看原文
[Analysis]\color{blue}{\texttt{[Analysis]}}
首先，对数据结构比较熟悉的同学应该知道，静态数组求区间最大公约数可以用 ST 表来解决。
事实上，ST 表的本质就是倍增算法。因此，只要是静态数组的问题，基本都可以用 ST 表解决。
只不过，对于求区间和、区间异或和之类的问题，每个数出现次数对最终答案是有影响的，因此 ST 表查询答案的时候也必须用 O(log⁡n)O(\log n) 的算法（一步一步跳着查询）。而区间最大最小值、区间最大公约数这些问题和每个数出现次数没有关系，可以直接 O(1)O(1) 查询。
式子很复杂，也无法用一般的数论方法化简。因此，只能考虑 dp。
设 gcd⁡i=1aAi\gcd\limits_{i=1}^{a} A_{i} 为第一段和，gcd⁡i=a+1bAi\gcd\limits_{i=a+1}^{b} A_{i} 为第二段和，以此类推。
记 fk,if_{k,i} 表示只考虑到第 ii 个数，求其前 kk 段和，且第 ii 个数必须划到第 kk 段和时所有方案的总和。gk,ig_{k,i} 表示只考虑到第 ii 个数，求其前 kk 段和，且第 ii 个数必须划到第 kk 段和时可行的区间划分的方案数。
最终答案即为：
∑i=7nf7,i\sum\limits_{i=7}^{n}f_{7,i}
则 ff 的转移方程为：
fk,i=∑j=1i−1(fk−1,j+gk−1,j×gcd⁡x=j+1iAx)f_{k,i}=\sum\limits_{j=1}^{i-1}\left ( f_{k-1,j} + g_{k-1,j} \times \gcd\limits_{x=j+1}^{i} A_{x} \right )
gg 的转移方程为：
gk,i=∑j=1i−1gk−1,jg_{k,i}=\sum\limits_{j=1}^{i-1}g_{k-1,j}
直接这么转移肯定会超时，考虑优化。显然 gg 可以用前缀和优化。
展开 ff 的转移方程：
fk,i=∑j=1i−1fk−1,j+∑j=1i−1gk−1,j×gcd⁡x=j+1iAxf_{k,i} = \color{red}{\sum\limits_{j=1}^{i-1} f_{k-1,j}}+\color{blue}{\sum\limits_{j=1}^{i-1} g_{k-1,j} \times \gcd\limits_{x=j+1}^{i} A_{x}}
显然，红色部分也可以用前缀和优化。考虑优化蓝色部分。
固定 ii，则 uj=gcd⁡x=j+1iAxu_{j}=\gcd\limits_{x=j+1}^{i} A_{x} 是一个变下限区间求最大公约数。区间右端点为 ii 是固定的。因此，uju_{j} 必然是 AiA_{i} 的约数，且 uju_{j} 必然是 uj+1u_{j+1} 的约数。故 uj≤uj+1u_{j} \leq u_{j+1}。
因此 uu 具有单调性，而 AiA_{i} 的约数最多为 log⁡Ai\log A_{i} 个，因此 uu 至多可以分为 log⁡Ai\log A_{i} 段，每段内 uu 值相同。可以用二分法求出区间分界点。
对于 uu 值相同的区间，即 gcd⁡x=j+1iAx\gcd\limits_{x=j+1}^{i} A_{x} 相同的区间，gk−1,jg_{k-1,j} 的和可以用前缀和求出。
总的时间复杂度 O(nlog⁡2n)O(n \log^{2} n)。
Code\color{blue}{\text{Code}}
CPP
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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...