「CF1327D」Infinite Path

发表于 分类于

$Link$

给你一个 $n$ 的排列 $p$，以及排列中每个数的颜色 $c$。

定义若 $c=a\times b$，则 $c_i=b_{a_i}$。

找到最小的正整数 $k$ 使得将 $p$ 变为 $p^k$ 后，存在一个 $i$ 使得 $c_i=c_{p_i}=c_{p_{p_i}}=\cdots$。

共有 $t$ 组数据。

$1\le t\le 10^4,\sum n\le 2\times 10^5$。

容易看出实际上是 $i$ 向 $p_i$ 连边后形成了一堆环，每个环是独立的。

找到一个 $k$ 使得每次跳 $k$ 步，经过的所有点颜色相同。

容易知道经过的点是 $\gcd (len,k)$ 的所有倍数，因此当 $k|len$ 时最优。

于是直接枚举 $len$ 的所有因子，暴力判断颜色就好了。

时间复杂度 $O(n\sqrt n)$。

$code$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <cmath>
using namespace std;
inline int read()
{
    int f = 1, x = 0;
    char ch;

    do{
        ch = getchar();
        if (ch == '-')
            f = -1;
    }while(ch < '0' || ch > '9');
    do{
        x = x * 10 + ch - '0';
        ch = getchar();
    }while(ch >= '0' && ch <= '9');
    return f * x;
}
const int N = 2e5;

int tt;
int n;
int p[N + 1], c[N + 1];
int d[N + 1];
int ans;
vector<int> v;

int main()
{
    tt = read();

    while (tt--) {
        n = read();
        for (int i = 1; i <= n; i++) {
            d[i] = 0;
            p[i] = read();
        }
        for (int i = 1; i <= n; i++)
            c[i] = read();
        ans = n;
        for (int i = 1; i <= n; i++) {
            if (!d[i]) {
                v.clear();
                int now = i;
                while (!d[now]) {
                    d[now] = 1;
                    v.push_back(now);
                    now = p[now];
                }
                bool flag = false;
                for (int j = 1; j <= v.size(); j++) {
                    if (v.size() % j)
                        continue;
                    for (int k = 0; k < j; k++) {
                        flag = true;
                        for (int now = k; now + j < v.size(); now += j) {
                            if (c[v[now]] != c[v[now + j]]) {
                                flag = false;
                                break;
                            }
                        }
                        if (flag)
                            break;
                    }
                    if (flag) {
                        ans = min(ans, j);
                        break;
                    }
                }
            }
        }
        printf("%d\n", ans);
    }

    return 0;
}