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

· · 题解

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

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

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

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

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

设 \gcd\limits_{i=1}^{a} A_{i} 为第一段和，\gcd\limits_{i=a+1}^{b} A_{i} 为第二段和，以此类推。

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

最终答案即为：

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

则 f 的转移方程为：

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 ) $$g_{k,i}=\sum\limits_{j=1}^{i-1}g_{k-1,j}$$ 直接这么转移肯定会超时，考虑优化。显然 $g$ 可以用前缀和优化。 展开 $f$ 的转移方程： $$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}}$$ 显然，红色部分也可以用前缀和优化。考虑优化蓝色部分。 固定 $i$，则 $u_{j}=\gcd\limits_{x=j+1}^{i} A_{x}$ 是一个变下限区间求最大公约数。区间右端点为 $i$ 是固定的。因此，$u_{j}$ 必然是 $A_{i}$ 的约数，且 $u_{j}$ 必然是 $u_{j+1}$ 的约数。故 $u_{j} \leq u_{j+1}$。 因此 $u$ 具有单调性，而 $A_{i}$ 的约数最多为 $\log A_{i}$ 个，因此 $u$ 至多可以分为 $\log A_{i}$ 段，**每段内 $u$ 值相同**。可以用二分法求出区间分界点。 对于 $u$ 值相同的区间，即 $\gcd\limits_{x=j+1}^{i} A_{x}$ 相同的区间，$g_{k-1,j}$ 的和可以用前缀和求出。 总的时间复杂度 $O(n \log^{2} n)$。 $\color{blue}{\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;
}