CF542C题解

Jefferyz / 2024-10-05 / 原文

传送门：https://codeforces.com/problemset/problem/542/C

我们把序列的映射关系看作$i\rightarrow f(i)$的边，要使$f(f(i))=f(i)$，显然存在$i$点距离不超过$1$的长度为$1$的自环。

推广到$f^{(k)}(x)$满足题意则会在距离$x$点距离不超过$k$的长度为$k$的环。我们要使$f^{(k)}(x)=f^{(k)}(\ f^{(k)}(x))$，成立，当前仅当存在一个长度为$z$的环，与$\ x\ $联通且距离不超过$k$。且$k|z$（因为需要绕一圈回到原点）。我们要使此关系对于任意$x$成立，则最小$k$为所有环长度的最小公倍数，若$k$小于所有点与最近环的距离，则需要将答案倍乘到$≥$此距离。

可以$O(n)$预处理所有环以及每个点与环的距离，具体见以下答案。总时间复杂度$O(nlog_2{n})$，瓶颈在于最大公约数。

#include <bits/stdc++.h>

#define int long long
using namespace std;

inline int read() {
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9') if (c == '-') flag = true;
    int res = c - '0';
    while ((c = getchar()) >= '0' && c <= '9') res = (res << 3) + (res << 1) + c - '0';
    return flag ? -res : res;
}

const int N = 201;

struct Edge {
    int v, next;
} e[N];

int head[N], cnt;

void add(int u, int v) {
    e[cnt].v = v;
    e[cnt].next = head[u];
    head[u] = cnt++;
}

int dis[N], c, b, flag, len[N], vis[N], v;

void dfs(int x) {
    if (vis[x] && vis[x] != v) return;
    if (vis[x] && vis[x] == v) {
        b = x;
        flag = 1;
        ++c;
        return;
    }
    vis[x] = v;
    for (int i = head[x]; ~i; i = e[i].next) dfs(e[i].v);
    if (x != b && flag) ++len[c];
    if (x == b) {
        ++len[c], flag = 0, b = 0;
        return;
    }
    if (!flag) dis[x] = dis[e[head[x]].v] + 1;
}

int gcd(int aa, int bb) { return bb ? gcd(bb, aa % bb) : aa; }

signed main() {
    memset(head, -1, sizeof head);
    int n = read();
    for (int i = 1; i <= n; ++i) {
        int u = read();
        add(i, u);
    }
    for (int i = 1; i <= n; ++i) if (!vis[i]) ++v, dfs(i);
    int mx = 0;
    for (int i = 1; i <= n; ++i) mx = max(mx, dis[i]);
    int ans = len[1];
    for (int i = 2; i <= c; ++i) ans = ans / gcd(ans, len[i]) * len[i];
    if (mx > ans) printf("%lld", mx % ans ? ans * (mx / ans + 1) : mx);
    else printf("%lld", ans);
    return 0;
}