CodeForces 1327D - Infinite Path

Problem

排列的$k$次幂代表一次移动变为移动$k$次。

然后就是可怕的卡时间了，先找出排列中所有的环和长度，然后对每个环进行遍历的时候只考虑步长$k$整除环的长度的情况，还需要先计算出来走$k$步到达的位置。

Solution

#include <iostream>
#include <string>
#include <vector>
#include <cstring>
using namespace std;

int n = 0, cnt = 0, len = 0;
int p[200005] = {};
int c[200005] = {};
int idx[200005] = {};
int off[200005] = {};
int nex[200005] = {};
bool vis[200005] = {};
vector<int> g[200005];

void dfs(int pos) {
  if (vis[pos]) return;
  vis[pos] = true;
  idx[pos] = cnt;
  off[pos] = len++;
  g[cnt].emplace_back(pos);
  dfs(p[pos]);
}

int main() {
  int T = 0;
  scanf("%d", &T);
  while (T--) {
    cnt = 0;
    memset(vis, 0, sizeof(vis));
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
      scanf("%d", &p[i]);
      p[i] = p[i] - 1;
    }
    for (int i = 0; i < n; ++i) {
      scanf("%d", &c[i]);
    }
    for (int i = 0; i < n; ++i) {
      if (!vis[i]) {
        len = 0;
        g[cnt].clear();
        dfs(i);
        ++cnt;
      }
    }
    int ans = n;
    for (int i = 0; i < cnt; ++i) {
      len = g[i].size();
      for (int j = 1; j <= len; ++j) {
        if (len % j == 0) {
          for (int k = 0; k < len; ++k) {
            vis[g[i][k]] = false;
            nex[g[i][k]] = g[i][(k + j) % len];
          }
          for (int k = 0; k < len; ++k) {
            if (!vis[g[i][k]]) {
              bool flag = true;
              int pos = nex[g[i][k]];
              while (pos != g[i][k]) {
                vis[pos] = true;
                if (c[pos] != c[g[i][k]]) {
                  flag = false;
                  break;
                }
                pos = nex[pos];
              }
              if (flag) {
                ans = min(ans, j);
                break;
              }
            }
          }
        }
      }
    }
    printf("%d\n", ans);
  }
  return 0;
}

<EOF>