题解 CF542C 【Idempotent functions】

素质玩家孙1超 · 2020-05-13 20:53:02 · 题解

首先暴力代码很好写(可以帮助更好理解题意)

但是答案可以达到千万级别，所以任然会TLE

打完暴力再看看题目

然后手玩数据

我随手打了一个例子

9
5 6 7 4 2 5 1 3 8

用暴力搞出原序列操作20次的

5 6 7 4 2 5 1 3 8
2 5 1 4 6 2 5 7 3
6 2 5 4 5 6 2 1 7
5 6 2 4 2 5 6 5 1
2 5 6 4 6 2 5 2 5
6 2 5 4 5 6 2 6 2
6//表示第六次是合要求的（下同）
5 6 2 4 2 5 6 5 6
2 5 6 4 6 2 5 2 5
6 2 5 4 5 6 2 6 2
9
5 6 2 4 2 5 6 5 6
2 5 6 4 6 2 5 2 5
6 2 5 4 5 6 2 6 2
12
5 6 2 4 2 5 6 5 6
2 5 6 4 6 2 5 2 5
6 2 5 4 5 6 2 6 2
15
5 6 2 4 2 5 6 5 6
2 5 6 4 6 2 5 2 5
6 2 5 4 5 6 2 6 2
18
5 6 2 4 2 5 6 5 6
2 5 6 4 6 2 5 2 5

然后发现，虽然答案会很大，但是每个位置的循环都不会很长，并且最后整个序列会循环

并且互相独立

所以我们想到对于每个位置，求出他的循环节开始的位置和长度

然后全部长度的最小公倍数就是整个序列的循环节

当整个序列循环一次后，就能得到答案

• 注意：若整个循环节还没有某个序列的最初循环位置大，那么要答案要加上循环节的大小直至大于等于某个序列的最初循环位置。（有点绕，可以详见代码）

核心代码：

n=R();
for(int i=1;i<=n;i++) a[i]=R();
for(int i=1;i<=n;i++)
{
    memset(vis,0,sizeof vis);
    x=a[i]; 
    num=1;
    vis[x]=num;
    x=a[x];
    while(!vis[x])
    {
        vis[x]=++num;
        x=a[x];
    }
    m=max(m,vis[x]);//m表示最大的初始循环位置
    num=num-vis[x]+1;
    ans=lcm(ans,(long long )num);//ans表示整个循环节的长度
}
int add=ans;
while(ans<m) ans+=add;//特判
printf("%lld",ans);