自动搬运

查看原文

来自洛谷，原作者为

	DeaphetS 什么时候才能回归绿名啊

搬运于2025-08-24 22:38:09，当前版本为作者最后更新于2022-07-13 10:50:33，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

本题涉及了关于线性筛、质因数分解、置换、分析数据范围特性等多种技巧，是一道难得的好题，为出题人点赞！

Hint 1

可以把每个 $p_i$ 看成从 $i$ 连向 $p_i$ 的一条有向边，这样整个图会由若干个互不相交的简单环构成（所有点的入度出度均为 $1$ ）。

可以通过分析得出， $P^k$ 的意义就相当于每个人一开始都在初始的 $i$ 号结点， $k$ 每次 $+1$ 就变成所有人在图上走一步。

于是我们得出了 $f(i,j)=0$ 的充要条件： $i,j$ 在同一个环上。

Hint 2

考虑对一个排列 $P$ 如何计算 $v(P)$ ，设 $i$ 号结点所在的环长为 $r_i$ ，则可以得出 $v(P)=\operatorname{lcm}\{r_1,r_2,\cdots,r_n\}$ ，这是因为所有点都同时回到原点需要保证每个人的步数都为 $r_i$ 的倍数。

接着考虑 $v(A_{ij})$ 的值，草稿纸上画一画就可以发现，把两个不同环上的点的出边进行交换，就会把两个环合并，因此 $v(A_{ij})$ 的值就为 $r_i+r_j$ 与其他环长取 $\operatorname{lcm}$ 的值。

到这一步实际上我们发现如果枚举 $i,j$ 并暴力计算 $\operatorname{lcm}$ ，那么可以得到一个看上去是 $O(n^3\log n)$ 的做法。

Hint 3

对上一步的暴力做法进行些许优化，对每个相同的 $r_i$ 其实是不用重复计算的，所以设环长的种类数为 $m$ ，能做到 $O(m^3\log n)$ 的复杂度。

这里需要进行对数据范围分析，注意到这里是 $m$ 个互不相同的数相加不超过 $n$ ，所以一定有 $\sum_{i=1}^m\le n$ ，计算得出 $m$ 是 $O(\sqrt n)$ 级别的，所以时间复杂度貌似可以优化到 $O(n\sqrt n\log n)$ 。

Hint 4

但是我们会发现 $\operatorname{lcm}$ 的值可能会很大并不能直接计算，所以需要对每个 $r_i$ 进行质因数分解，最后在每个质因子上计算指数的最大值得出结果，这样单次计算 $\operatorname{lcm}$ 的时间复杂度为 $O(m\sqrt n+cnt_{prime}\cdot\log\log n)$ 。

这里可以利用线性筛的性质来加速质因数分解的过程，注意到每次线性筛筛到一个数时，一定是被他的最小质因子筛到，于是可以预处理记录下每个数字对应的最小质因子，这样单次质因数分解的时间复杂度可以优化到 $O(\log n)$ 。

除此之外，我们还可以在每次分解质因数时直接质因子判断对应指数的值，并判断是否乘上去，如果采用 map 或 set 来记录，这样单次计算 $\operatorname{lcm}$ 的复杂度变成了 $O(m\log^2 m)$ ，总时间复杂度为 $O(n\sqrt n\log^2 n)$ 。

如果在判断每个质因子对应的最大指数时做到 $O(1)$ 的维护，那么就是 $O(n\sqrt n\log n)$ 的时间复杂度，期望得分 80 ，如果能做到常数优秀且熟练掌握卡常技巧是完全有机会通过此题的。

Hint 5

继续优化求 $\operatorname{lcm}$ 的方法，我们可以预先求出所有数字的 $\operatorname{lcm}$ ，然后记录每个质因子对应的三个最大指数（因为后面要删掉两个数），这样每次删数的时候就可以现场质因数分解 $O(\log^2 n)$ 维护 $\operatorname{lcm}$ ，添加一个数字的时候也能够当场维护。

另外，也可以直接用 multiset 记录每个质因子对应的指数集合，同样也是 $O(\log^2 n)$ 的维护复杂度。

总时间复杂度 $O(n\log^2n)$ ，已经足够通过此题。

#include<bits/stdc++.h>
using namespace std;
#define N 500050
#define LL long long
#define MOD 1000000007
int T,n,a[N],r[N],vis[N];
int cnt,cntR,p[N],v[N],LCM,m,ans;
vector<pair<int,int>>d;
multiset<int>s[N];
LL qow(LL x,LL y){return y?(y&1?x*qow(x,y-1)%MOD:qow(x*x%MOD,y/2)):1;}
void add(int x)
{
	while(x>1){
		int p=v[x],c=0,k=(*s[p].rbegin());
		while(v[x]==p)x/=v[x],c++;
		if(c>k)LCM=1ll*LCM*qow(p,c-k)%MOD;
		s[p].insert(c);
	}
}
void del(int x)
{
	while(x>1){
		int p=v[x],c=0,k;
		while(v[x]==p)x/=v[x],c++;
		s[p].erase(s[p].find(c));
		k=(*s[p].rbegin());
		if(k<c)LCM=1ll*LCM*qow(p,MOD-1+k-c)%MOD;
	}
}
void init()
{
	LCM=1;
	cntR=0;
	d.clear();
	for(int i=1;i<=cnt;i++)s[p[i]].clear(),s[p[i]].insert(0);
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		r[i]=vis[i]=0;
	}
	for(int i=1;i<=n;i++)if(!vis[i]){
		int x=i,c=1;
		while(a[x]!=i)vis[x]=1,c++,x=a[x];
		add(c);
		vis[x]=1;
		r[++cntR]=c;
	}
	sort(r+1,r+cntR+1);
	for(int i=1;i<=cntR;i++){
		if(d.empty() || r[i]!=d.back().first)
			d.push_back(make_pair(r[i],1));
		else d[d.size()-1].second++;
	}
	m=d.size(),ans=0;
	for(int i=0;i<m;i++){
		del(d[i].first);
			for(int j=i+1;j<m;j++){
			int res=2ll*(1ll*d[i].first*d[i].second%MOD)*(1ll*d[j].first*d[j].second%MOD)%MOD;
			int x=d[i].first+d[j].first;
			del(d[j].first);
			add(x);
			ans=(1ll*res*LCM+ans)%MOD;
			del(x);
			add(d[j].first);
		}
		if(d[i].second>1){
			int res=1ll*(1ll*d[i].first*d[i].second%MOD)*(1ll*d[i].first*(d[i].second-1))%MOD;
			int x=d[i].first+d[i].first;
			del(d[i].first);
			add(x);
			ans=(1ll*res*LCM+ans)%MOD;
			del(x);
			add(d[i].first);
		}
		add(d[i].first);
	}
	printf("%d\n",ans);
}
int main()
{
	v[1]=1;
	for(int i=2;i<N;i++){
		if(!v[i])v[i]=i,p[++cnt]=i;
		for(int j=1;j<=cnt && i*p[j]<N;j++){
			v[i*p[j]]=p[j];
			if(i%p[j]==0)break;
		}
	}
	scanf("%d",&T);
	while(T--)init();
}