题解 P8338 [AHOI2022] 排列

· · 题解

什么题都不会做，只能水题解了。作为已死去的JXOI2022的签到题，我还是要会做的，虽然把题面的第二个公式的第二个 p 看成了 P 推了半天样例。

首先看到排列、换来换去的元素、可以互相表示的元素不计贡献，很快能猜出结论：环内没有贡献，环外元素交换大概是相加。

接下来就可以小证一下了：

首先 i \to a_i，构建出一张图。

因为 p_i^k=p_{p_{p_{p_{p_i}}}}（k+1 个 p），不难发现周期是图上的环长。

所以有： V(P)=lcm(\text{P中所有环的长度})

交换不在同一个环上的 $a_i,a_j$ 时，令 $pre_i \to i \to a_i \to^{若干条边} pre_i$，$pre_j \to j \to a_j \to^{若干条边} pre_j$，交换后就是 $pre_i \to i \to a_j \to^{若干条边} pre_j \to j \to a_i \to^{若干条边} pre_i$，成了一个环，且新环的环长为原两环长的和。 发现：环长相同的环和其他环贡献相同，所以把环长相同的环合并到一起。 一个结论：设有 $x$ 个不同长度的环，最坏情况是 $1,2,3\dots x$，于是 $\dfrac{(x+1)x}{2}=n$，$x\approx\sqrt n$，所以枚举两两环长是 $O(n)$ 的。 考虑怎么计算贡献：（令 $cnt(i)$ 为 环长为 $i$ 的个数，$lcm$ 为交换之后的所有环长的 $lcm$） + 长度为 $i<j$ 的两个环：$2\times i\times cnt(i) \times j \times cnt(j) \times lcm

至此，问题转化为了有一个集合，每次询问两个环长 i,j，删除集合中的 i,j，加入 i+j 后的整个集合的 lcm，每次询问独立。

怎么快速维护 lcm 呢？可以考虑质因子，lcm 等价于所有数的每个质因子选次数最大的乘起来。发现一个元素最多删除两次，所以我们只用维护每个质因子的前三大，就可以维护出每个质因子当前的最大次数，从而就可以维护出 lcm。

因为一个数的不同质因子是 log 级别的，删除和插入都可以枚举这个数的所有质因子来实现，使用线性筛辅助分解质因数是 log 的，所以总复杂度为 O(\sqrt n \times \sqrt n \times log n=nlogn)，但是我的实现貌似有点烂（还带了个逆元的 log，但是懒得改了）。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int _=1e6+5,mod=1e9+7;
int n,a[_],ff[_],sz[_],Fmax[_],smax[_],tmax[_],lcm;
int minp[_],pr[_],pn;
bool vis[_];
int find(int x){return ff[x]==x?x:ff[x]=find(ff[x]);}
int qpow(int x,int y,int r=1){
    for(;y;y>>=1){
        if(y&1) r=r*x%mod;
        x=x*x%mod;
    }
    return r;
}
void init(int n){
    for(int i=2;i<=n;++i){
        if(!vis[i]) pr[++pn]=i,minp[i]=i;
        for(int j=1;j<=pn&&pr[j]*i<=n;++j){
            vis[pr[j]*i]=1;
            minp[pr[j]*i]=pr[j];
            if(i%pr[j]==0) break;
        }
    }
}
void chkmax(int x,int y){
    if(Fmax[x]>=y){
        if(smax[x]>=y) tmax[x]=max(tmax[x],y);
        else tmax[x]=smax[x],smax[x]=y;
    }
    else tmax[x]=smax[x],smax[x]=Fmax[x],Fmax[x]=y;
}
void chkban(int x,int y){
    if(Fmax[x]>0){
        if(Fmax[x]==y){
            lcm=lcm*qpow(qpow(x,y),mod-2)%mod;
            if(smax[x]>0) lcm=lcm*qpow(x,smax[x])%mod;
            else lcm=lcm*qpow(x,tmax[x])%mod;
            Fmax[x]=-y;
        }
        else if(smax[x]==y) smax[x]=-y;
    }
    else{
        if(smax[x]>0){
            if(smax[x]==y) lcm=lcm*qpow(qpow(x,y),mod-2)%mod,lcm=lcm*qpow(x,tmax[x])%mod,smax[x]=-y;
        }
        else cout<<"ERROR!",exit(0);
    }
}
void chkunban(int x,int y){
    if(smax[x]==-y) smax[x]=-smax[x];
    else if(Fmax[x]==-y) Fmax[x]=-Fmax[x];
}
void chkupd(int x,int y){
    if(Fmax[x]>=0){
        if(Fmax[x]<y) lcm=lcm*qpow(qpow(x,Fmax[x]),mod-2)%mod,lcm=lcm*qpow(x,y)%mod;
    }
    else{
        if(smax[x]>=0){
            if(smax[x]<y) lcm=lcm*qpow(qpow(x,smax[x]),mod-2)%mod,lcm=lcm*qpow(x,y)%mod;
        }
        else{
            if(tmax[x]<y) lcm=lcm*qpow(qpow(x,tmax[x]),mod-2)%mod,lcm=lcm*qpow(x,y)%mod;
        }
    }
}
void solve(){
    cin>>n;
    memset(Fmax,0,sizeof Fmax),memset(smax,0,sizeof smax),memset(tmax,0,sizeof tmax);
    lcm=1;
    for(int i=1;i<=n;++i) cin>>a[i],ff[i]=i,sz[i]=1;
    for(int i=1;i<=n;++i){//找环
        int x=find(a[i]),y=find(i);
        if(x^y) ff[x]=find(y),sz[y]+=sz[x];
    }
    vector<int> V;
    for(int i=1;i<=n;++i) if(ff[i]==i) V.push_back(sz[i]);
    sort(V.begin(),V.end());
    vector<pair<int,int>> V2,VV[V.size()];;//V2为合并去重环长，VV[i]为V2[i]这个环的质因子
    int lst=0;
    for(auto x:V){//去重合并
        if(lst==x) ++V2[V2.size()-1].second;
        else V2.push_back({x,1});
        lst=x;
    }
    // assert(V2.size()<=sqrt(n)+1);
    for(int i=0;i<V.size();++i){//质因子插入集合中
        int x=V[i];
        while(x^1){
            int p=minp[x],res=0;
            while(minp[x]==p) x/=p,++res;
            chkmax(p,res);
        }
    }
    for(int i=0;i<V2.size();++i){//质因子存起来
        int x=V2[i].first;
        while(x^1){
            int p=minp[x],res=0;
            while(minp[x]==p) x/=p,++res;
            VV[i].push_back({p,res});
        }
    }
    for(int i=2;i<=pr[pn];++i) if(Fmax[i]) lcm=lcm*qpow(i,Fmax[i])%mod;//求lcm
    int Blcm=lcm,ans=0;
    for(int i=0;i<V2.size();++i){
        for(auto x:VV[i]) chkban(x.first,x.second);//删数
        int BBlcm=lcm;
        for(int j=i;j<V2.size();++j){
            if(i==j&&V2[i].second<2) continue;//没有2个长度相同的环
            for(auto x:VV[j]) chkban(x.first,x.second);
            int y=V2[i].first+V2[j].first;
            while(y^1){
                int p=minp[y],res=0;
                while(p==minp[y]) y/=p,++res;
                chkupd(p,res);//算插入后的lcm
            }
            if(i==j) ans=(ans+1ll*V2[i].first%mod*V2[i].first%mod*(V2[i].second*(V2[i].second-1)%mod)%mod*lcm%mod)%mod;
            else ans=(ans+1ll*2*V2[i].second%mod*V2[i].first%mod*V2[j].second%mod*V2[j].first%mod*lcm%mod)%mod;
            for(auto x:VV[j]) chkunban(x.first,x.second);//恢复
            lcm=BBlcm;
        }
        for(auto x:VV[i]) chkunban(x.first,x.second);
        lcm=Blcm;
    }
    cout<<ans<<'\n';
}
signed main(){
    init(1000000);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t; cin>>t;
    while(t--) solve();
    return 0;
}