自学内容网 自学内容网

洛谷 P11626 题解

[Problem   Discription] \color{blue}{\texttt{[Problem Discription]}} [Problem Discription]

给定长度为 n n n 的数组 A 1 ⋯ n A_{1 \cdots n} A1n,求

∑ a = 1 n ∑ b = a + 1 n ∑ c = b + 1 n ∑ d = c + 1 n ∑ e = d + 1 n ∑ f = e + 1 n ∑ g = f + 1 n ( gcd ⁡ i = 1 a A i + gcd ⁡ i = a + 1 b A i + gcd ⁡ i = b + 1 c A i + gcd ⁡ i = c + 1 d A i + gcd ⁡ i = d + 1 e A i + gcd ⁡ i = e + 1 f A i + gcd ⁡ i = f + 1 g A i ) \sum\limits_{a=1}^{n}\sum\limits_{b=a+1}^{n}\sum\limits_{c=b+1}^{n}\sum\limits_{d=c+1}^{n}\sum\limits_{e=d+1}^{n}\sum\limits_{f=e+1}^{n}\sum\limits_{g=f+1}^{n}\left ( \gcd\limits_{i=1}^{a}A_{i}+\gcd \limits_{i=a+1}^{b} A_{i}+\gcd\limits_{i=b+1}^{c} A_{i} + \gcd \limits_{i=c+1}^{d} A_{i} +\gcd\limits_{i=d+1}^{e} A_{i} +\gcd\limits_{i=e+1}^{f} A_{i} +\gcd\limits_{i=f+1}^{g} A_{i} \right ) a=1nb=a+1nc=b+1nd=c+1ne=d+1nf=e+1ng=f+1n(i=1gcdaAi+i=a+1gcdbAi+i=b+1gcdcAi+i=c+1gcddAi+i=d+1gcdeAi+i=e+1gcdfAi+i=f+1gcdgAi)

998244353 998244353 998244353 取模的结果。

其中 gcd ⁡ i = l r x i \gcd\limits_{i=l}^{r} x_{i} i=lgcdrxi 表示 x l , x l + 1 , … , x r x_{l},x_{l+1},\dots,x_{r} xl,xl+1,,xr 的最大公约数。

7 ≤ n ≤ 1 × 1 0 5 , 1 ≤ x i ≤ 1 × 1 0 9 7 \leq n \leq 1 \times 10^{5}, 1\leq x_{i} \leq 1 \times 10^{9} 7n1×105,1xi1×109

[Analysis] \color{blue}{\texttt{[Analysis]}} [Analysis]

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

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

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

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

gcd ⁡ i = 1 a A i \gcd\limits_{i=1}^{a} A_{i} i=1gcdaAi 为第一段和, gcd ⁡ i = a + 1 b A i \gcd\limits_{i=a+1}^{b} A_{i} i=a+1gcdbAi 为第二段和,以此类推。

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

最终答案即为:

∑ i = 7 n f 7 , i \sum\limits_{i=7}^{n}f_{7,i} i=7nf7,i

f f f 的转移方程为:

f k , i = ∑ j = 1 i − 1 ( f k − 1 , j + g k − 1 , j × gcd ⁡ x = j + 1 i A x ) 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 ) fk,i=j=1i1(fk1,j+gk1,j×x=j+1gcdiAx)

g g g 的转移方程为:

g k , i = ∑ j = 1 i − 1 g k − 1 , j g_{k,i}=\sum\limits_{j=1}^{i-1}g_{k-1,j} gk,i=j=1i1gk1,j

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

展开 f f f 的转移方程:

f k , i = ∑ j = 1 i − 1 f k − 1 , j + ∑ j = 1 i − 1 g k − 1 , j × gcd ⁡ x = j + 1 i A x f_{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}} fk,i=j=1i1fk1,j+j=1i1gk1,j×x=j+1gcdiAx

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

固定 i i i,则 u j = gcd ⁡ x = j + 1 i A x u_{j}=\gcd\limits_{x=j+1}^{i} A_{x} uj=x=j+1gcdiAx 是一个变下限区间求最大公约数。区间右端点为 i i i 是固定的。因此, u j u_{j} uj 必然是 A i A_{i} Ai 的约数,且 u j u_{j} uj 必然是 u j + 1 u_{j+1} uj+1 的约数。故 u j ≤ u j + 1 u_{j} \leq u_{j+1} ujuj+1

因此 u u u 具有单调性,而 A i A_{i} Ai 的约数最多为 log ⁡ A i \log A_{i} logAi 个,因此 u u u 至多可以分为 log ⁡ A i \log A_{i} logAi 段,每段内 u u u 值相同。可以用二分法求出区间分界点。

对于 u u u 值相同的区间,即 gcd ⁡ x = j + 1 i A x \gcd\limits_{x=j+1}^{i} A_{x} x=j+1gcdiAx 相同的区间, g k − 1 , j g_{k-1,j} gk1,j 的和可以用前缀和求出。

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

Code \color{blue}{\text{Code}} 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;
}

原文地址:https://blog.csdn.net/ZHUYINGYE_123456/article/details/145432149

免责声明:本站文章内容转载自网络资源,如侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!