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

george0929 · 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;
}