P14523-solution

igAC · 2025-11-17 17:16:03 · 题解

\text{Description}

link

定义一个正整数序列是好的，当且仅当对任意正整数 k，若序列中存在 k 的倍数，则所有 k 的倍数在序列中的位置连续。例如 [1, 2, 6, 3] 是好的，而 [1, 2, 3, 6] 不是好的，因为该序列中 2 的倍数在序列中的位置分别是 2, 4，并不是连续的一段。

对于一个长度为 m 的正整数序列 b，定义 f(b) 为满足以下条件的好的正整数序列 b' 的数量：

• 若 b_i > 1，则 b'_i = b_i（1 \le i \le m）。

爱莉有一个长度为 n 的正整数序列 a_1, \ldots, a_n，她向你提出了 q 个问题，每次给出两个数 l, r，你要求出 \sum_{x = l}^r \sum_{y = x}^r f(a[x, y]) 的值对 10^9 + 7 取模的结果。

注：a[x, y] 表示序列 a 的子串 [a_x, \ldots, a_y]。\operatorname{LCM} 表示若干个正整数的最小公倍数。

\text{Solution}

考虑题目中好的序列的充要条件，容易发现是对于每个质数 p，序列在 p 上的指数是单峰的。

知道了这个我们先考虑 \text B 性质怎么做，即判定问题。

若 (l,r) 是合法的，那么 (l,r-1),(l+1,r) 都是合法的，也就是说若固定左端点则右端点是一个区间，并且单调不降。

显然每个质因数是独立的，我们对于每个质因数单独做，最后取 \min 即可。

而对于每一个质因数，合法区间一定不可能跨过一段 0，于是我们只需要考虑一个连续段，这个是简单的，但是要注意一个单峰序列的最后相同一段是可以作为下个单峰序列的开头的，需要特殊处理。

做完之后扫描线即可，然后就可以获得 52 分的高分，得分很高了所以我们按照这个思路往后想。

考虑加进来 1 怎么做。

容易发现 1 是不影响区间合法性的，然后我们考虑 1 的贡献。

发现处于不同连通块的 1 的贡献互不影响并且答案可以刻画成对以下问题计数：

长度为 m 的序列，对于每个质因数，序列中每个数在这个质因数上的指数在 [0,r_i] 之间，并且是不降的。

考虑对序列进行差分，那么问题就变为计数元素非负且和 \le r_i 的序列个数，=r_i 的情况是经典的 r_i 个相同小球放进 m 个不同的盒子里，盒子可以为空的方案数，\le r_i 的情况我们开一个新的盒子充当“垃圾桶”的角色即可。

考虑从右往左扫描线，分三种情况讨论：

所以我们要支持区间乘，维护区间历史和，上线段树即可。

\text{Code}

历史和线段树用矩阵维护是可以过的，赞美出题人。

时间复杂度 O(n\omega(V)+kn \log n)，k 是矩阵乘法的复杂度。

#include<bits/stdc++.h>
#define ll long long
#define Mod 1000000007
#define N 500005
#define M 500000
using namespace std;
int read(){
    int x=0,f=1,ch=getchar();
    for(;!isdigit(ch);ch=getchar()) f=(ch=='-')?-1:1;
    for(;isdigit(ch);ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
    return x*f;
}
int add(int x,int y){return x+y>=Mod?x+y-Mod:x+y;}
int del(int x,int y){return add(x,Mod-y);}
int mul(int x,int y){return ((ll)x*y)%Mod;}
void Add(int &x,int y){x=add(x,y);}
void Del(int &x,int y){x=del(x,y);}
void Mul(int &x,int y){x=mul(x,y);}
int n,m,q,a[N],b[N],R[N],lst[N],L[N],w[N],tmp[N];
int prime[N],tot,g[N],t[N],p[N],ans[N],pre[N],vv[N],cnt;
int Nxt[N],fac[N<<1],inv[N<<1];
bool vis[N],Vis[N];
vector<pair<int,int>>vec[N];
vector<pair<int,int>>que[N];
struct Matrix{
    int c[2][2];
    Matrix(){c[0][0]=c[0][1]=c[1][0]=c[1][1]=0;}
    friend Matrix operator * (const Matrix &a,const Matrix &b){
        Matrix c;
        c.c[0][0]=add(mul(a.c[0][0],b.c[0][0]),mul(a.c[0][1],b.c[1][0]));
        c.c[0][1]=add(mul(a.c[0][0],b.c[0][1]),mul(a.c[0][1],b.c[1][1]));
        c.c[1][0]=add(mul(a.c[1][0],b.c[0][0]),mul(a.c[1][1],b.c[1][0]));
        c.c[1][1]=add(mul(a.c[1][0],b.c[0][1]),mul(a.c[1][1],b.c[1][1]));
        return c;
    }
    friend Matrix operator + (const Matrix &a,const Matrix &b){
        Matrix c;
        c.c[0][0]=add(a.c[0][0],b.c[0][0]);
        c.c[0][1]=add(a.c[0][1],b.c[0][1]);
        c.c[1][0]=add(a.c[1][0],b.c[1][0]);
        c.c[1][1]=add(a.c[1][1],b.c[1][1]);
        return c;
    }
    bool empty(){return (c[0][0]==1 && !c[0][1] && !c[1][0] && c[1][1]==1);}
    void init(){c[0][0]=1,c[0][1]=0,c[1][0]=0,c[1][1]=1;}
}I,II;
struct Segment{
    int l,r;
    Matrix sum,tag;
}node[N<<2];
void getnew(int p){node[p].sum=node[p<<1].sum+node[p<<1|1].sum;}
void build(int p,int l,int r){
    node[p].l=l,node[p].r=r,node[p].tag.init();
    if(l==r){
        node[p].sum.c[0][1]=1;
        return;
    }
    int mid=(l+r)>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
}
void spread(int p){
    if(!node[p].tag.empty()){
        node[p<<1].sum=node[p<<1].sum*node[p].tag;
        node[p<<1|1].sum=node[p<<1|1].sum*node[p].tag;
        node[p<<1].tag=node[p<<1].tag*node[p].tag;
        node[p<<1|1].tag=node[p<<1|1].tag*node[p].tag;
        node[p].tag.init();
    }
}
void change(int p,int l,int r,Matrix v){
    if(l>r) return;
    if(l<=node[p].l && node[p].r<=r){
        node[p].sum=node[p].sum*v;
        node[p].tag=node[p].tag*v;
        return;
    }
    spread(p);
    int mid=(node[p].l+node[p].r)>>1;
    if(l<=mid) change(p<<1,l,r,v);
    if(r>mid) change(p<<1|1,l,r,v);
    getnew(p);
}
Matrix query(int p,int l,int r){
    if(l<=node[p].l && node[p].r<=r) return node[p].sum;
    spread(p);
    int mid=(node[p].l+node[p].r)>>1;
    if(r<=mid) return query(p<<1,l,r);
    else if(l>mid) return query(p<<1|1,l,r);
    else return query(p<<1,l,r)+query(p<<1|1,l,r);
}
Matrix work(int v){
    Matrix r;r.init(),r.c[1][1]=v;
    return r;
}
void getprime(){
    for(int i=2;i<=M;++i){
        if(!vis[i]) prime[++tot]=i,g[i]=t[i]=i,p[i]=1;
        for(int j=1;j<=tot && i*prime[j]<=M;++j){
            vis[i*prime[j]]=true;
            if(i%prime[j]==0){
                t[i*prime[j]]=t[i]*prime[j];
                g[i*prime[j]]=prime[j];
                p[i*prime[j]]=p[i]+1;
                break;
            }
            g[i*prime[j]]=t[i*prime[j]]=prime[j],p[i*prime[j]]=1;
        }
    }
}
int qpow(int a,int b){
    int res=1;
    while(b){
        if(b&1) Mul(res,a);
        Mul(a,a);
        b>>=1;
    }
    return res;
}
void init(){
    fac[0]=1;
    for(int i=1;i<=(M<<1);++i) fac[i]=mul(fac[i-1],i);
    inv[M<<1]=qpow(fac[M<<1],Mod-2);
    for(int i=(M<<1);i>=1;--i) inv[i-1]=mul(inv[i],i);
}
int C(int n,int m){
    if(n<m || n<0 || m<0) return 0;
    return mul(fac[n],mul(inv[m],inv[n-m]));
}
int S(int n,int m){return C(n+m-1,m-1);}
int main(){
//  FILE3("icedrop4");
    n=read(),q=read(),getprime(),init();
    I.init(),I.c[1][0]=1,II.init(),II.c[1][0]=-1;
    for(int i=1;i<=n;++i) b[i]=read();
    for(int i=1;i<=n;++i) if(b[i]!=1) a[++m]=b[i],pre[m]=i;
    if(!m){
        while(q--){
            int l=read(),r=read();
            printf("%d\n",mul(r-l+1,mul(r-l+2,(Mod+1)/2)));
        }
        return 0;
    }
    pre[m+1]=n+1;
    for(int i=1;i<=m;++i){
        int x=a[i];
        while(x!=1){
            if(lst[g[x]] && lst[g[x]]<i-1) vec[g[x]].push_back({L[g[x]],lst[g[x]]}),lst[g[x]]=L[g[x]]=i;
            else if(lst[g[x]]) lst[g[x]]=i;
            else lst[g[x]]=L[g[x]]=i;
            x/=t[x];
        }
    }
    for(int i=2;i<=M;++i) if(lst[i]) vec[i].push_back({L[i],lst[i]});
    for(int i=1;i<=m;++i) R[i]=m;
    for(int P=2;P<=M;++P){
        if(vec[P].empty()) continue;
        vec[P].push_back({m+1,m+1});
        for(int mm=0;mm+1<vec[P].size();++mm){
            int l=vec[P][mm].first,r=vec[P][mm].second;
            if(l==n+1) break;
            w[l-1]=w[r+1]=0;
            for(int i=l;i<=r;++i){
                w[i]=0;int x=a[i];
                while(x%P==0) x/=P,++w[i];
            }
            for(int i=l;i<=r;++i){
                int j=i;bool dn=false;
                for(;j+1<=r;++j){
                    if(dn && w[j+1]>w[j]) break;
                    if(w[j+1]<w[j]) dn=true;
                }
                int res=j;
                if(j==r){
                    for(int k=i;k<=j;++k) R[k]=min(R[k],vec[P][mm+1].first-1);
                    break;
                }
                while(dn && w[j]==w[j-1]) --j;
                if(dn) --j;
                for(int k=i;k<=j;++k) R[k]=min(R[k],res);
                i=j;
            }
        }
    }
    for(int i=m-1;i>=1;--i) R[i]=min(R[i],R[i+1]);
    for(int i=1;i<=m;++i) ++R[i];
    for(int i=1;i<=m;++i) tmp[pre[i]]=pre[R[i]]-1;
    for(int i=1;i<=n;++i) R[i]=tmp[i];
    R[n+1]=n;
    for(int i=n;i>=1;--i) if(!R[i]) R[i]=R[i+1];
    for(int i=1;i<=q;++i){
        int l=read(),r=read();
        que[l].push_back({r,i});
    }
    for(int i=1;i<=n;++i) a[i]=b[i];
    Nxt[n+1]=n+1;
    for(int i=n;i>=1;--i){
        if(i+1<=n && a[i+1]!=1) Nxt[i]=i+1;
        else Nxt[i]=Nxt[i+1];
    }
    build(1,1,n);
    for(int l=n;l>=1;--l){
        change(1,R[l]+1,n,work(0));
        int gg=-1;
        if(a[l]==1 && Nxt[l]!=n+1){
            int x=a[Nxt[l]],len=Nxt[l]-l,res=1;
            while(x!=1){
                Mul(res,S(p[x],len+1));
                x/=t[x];
            }
            change(1,Nxt[l],n,work(res)),gg=res;
        }
        else if(a[l]!=1){
            for(int i=l+1;i<Nxt[l];++i){
                int x=a[l],len=i-l,res=1;
                while(x!=1){
                    Mul(res,S(p[x],len+1));
                    x/=t[x];
                }
                change(1,i,i,work(res));
            }
            if(Nxt[l]!=n+1){
                cnt=0;
                {
                    int x=a[l];
                    while(x!=1){
                        vv[++cnt]=g[x];
                        x/=t[x];
                    }
                }
                {
                    int x=a[Nxt[l]];
                    while(x!=1){
                        vv[++cnt]=g[x];
                        x/=t[x];
                    }
                }
                int res=1;
                for(int i=1;i<=cnt;++i){
                    int x=vv[i];
                    if(Vis[x]) continue;
                    Vis[x]=true;
                    int c1=0,c2=0;
                    {
                        int xx=a[l];
                        while(xx%x==0) ++c1,xx/=x;
                    }
                    {
                        int xx=a[Nxt[l]];
                        while(xx%x==0) ++c2,xx/=x;
                    }
                    int len=Nxt[l]-l-1;
                    Mul(res,S(abs(c1-c2),len+1));
                }
                for(int i=1;i<=cnt;++i) Vis[vv[i]]=false;
                change(1,Nxt[l],n,work(res));
            }
        }
        change(1,l,n,I);
        for(auto [r,i]:que[l]) ans[i]=query(1,l,r).c[0][0];
        if(~gg) change(1,Nxt[l],n,work(qpow(gg,Mod-2)));
    }
    for(int i=1;i<=q;++i) printf("%d\n",ans[i]);
    return 0;
}