【NOIP】模拟赛--绵阳南山中学#12(比赛密码MX-AK-SX)

---

T1

首先易得本题就是一个基环树森林，所以每个连通块最多只有一个环

<1>法一(本蒟蒻场上的写法)：倍增$O(t\times nlog(n))$，这里仅供参考

Details

/*
首先最开始看到这个题以及范围思路立马到倍增上面了
预处理跳跃点，只需要两个点一起跳的时候不会到同一个点上就可以了
因为如果他们存在路径在相同步数到达同一个点，则说明他们后面的路径也一定重合
但现在时间复杂度瓶颈在 n^2 枚举点对上，思考优化方法 

但是这个题就是个基环树不是吗 

画了一下图，大概有头绪了，只要跳的够多，肯定会到一个相同点上的对吧
相反，如果这两个点没有交集，则跳的再多也不会重合对吧
所以统计在他之后的不同值就行了 
主要现在问题在于不清楚能不能存在多余步数 
*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long

const int N=1e5+10;

int n, logn;
int idx[N], vis[N]; 
int rode[17][N];

void updata()
{
	for( int i=logn;i>=0;i-- )
		for( int j=1;j<=n;j++ )
			if( rode[i][idx[j]] )
				idx[j]=rode[i][idx[j]];
	for( int i=1;i<=n;i++ )
		vis[idx[i]]++;
}

void sovel()
{
	cin>>n;
	logn=log2( n );
	for( int i=1;i<=n;i++ )
		cin>>rode[0][i], idx[i]=i;
	for( int pow=1;pow<=logn;pow++ )
		for( int i=1;i<=n;i++ )
			rode[pow][i]=rode[pow-1][rode[pow-1][i]];
	updata();	
	ll ans=0;
	for( int i=1;i<=n;i++ )
		ans+=( n-i+1-vis[idx[i]] ), vis[idx[i]]--;
	cout<<ans<<"\n";
}

int main()
{
	freopen( "a.in","r",stdin );
	freopen( "a.out","w",stdout );
	ios::sync_with_stdio( false );
	cin.tie( nullptr ), cout.tie( nullptr ); 
	int t;
	for( cin>>t;t;t-- )
		sovel();
} 

<2>法2：std的$O(n)$写法

如果两个点$x,y$它们走$k$步会到达同一个点上，则它们一定会先到一个环上

任取环上一个点，求到其他点的距离$dis$，设环长为$c$，则如果$dis_x\equiv dis_y\pmod c$则点对$(x,y)$不满足条件

总的可能为$C_n^2$那么对于每个联通块，假设有$cnt_i$个满足$dis_x\equiv i\pmod c$的点$x$，将答案减去$C_{cnt_i}^2$即可