ABC371G 题解

· · 题解

题意

给定两个排列 A 与 P，定义一次操作表示对于所有的 1\le i \le n，将 A_i 替换为 A_{P_i}。要求进行任意非负整数次操作，求能得到的字典序最小的排列。

题解

我们由 i 向 P_i 连一条有向边，那么可以得到一张图。考虑到现在一次操作实际上就是每个下标步进一次。

这时我们发现，确定操作次数，最终的排列就确定；换句话说，确定某一个点移动多少步，整个排列就确定。由此，结合要让字典序最小，很自然地考虑到要让每个环上的第一个位置最小。

但是这样可能冲突。考虑有两个大小为 3 和 6 的环，假设第一个环上移动 2 步最优，第二个环上移动 1 步最优。这时无论怎么操作，两个环都无法同时最优。换句话说，这两个同余方程没有公共解。

由于我们还要保证字典序最小，那么显然是尽量满足前面的环，即最小位置在最前面的环。后面的环怎么办？考虑枚举每个环上移动的步数 k，使得 k 和前面的同余方程不冲突，在此条件下满足字典序尽可能小（即最小位置放尽可能小的数）。

怎么判断某个 k 是否满足前面的同余方程？考虑到这个同余方程的模数是前面所有环长的 \text{lcm}，是阶乘级别的，没法直接做（然而官方题解拿 Python 水了）。考虑到

x\equiv a \pmod m \Leftrightarrow x\equiv a_i\pmod {m_i^{\alpha_i}}

其中 m_i, \alpha_i 是 m 的标准分解。

那么可以分解出环长的质因子。设 f(p) 表示当前同余方程的解模 p 的值。那么枚举操作次数 k 的同时，要满足对环长的每一个质因子 p，k \bmod p 都和 f(p) 相同。满足这个条件的情况下，再让字典序尽可能小。

于是我们做完了。

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
const int N = 2e5 + 10;
int ps[N], minp[N], res[N], z[N], p[N], w[N], f[N], nr = 0;
bool vis[N];

void sieve (void)
{
    for (int i = 2; i < N; i++) {
        if (!minp[i]) ps[++nr] = i, minp[i] = i;
        for (int j = 1; ps[j] * i < N; j++) {
            minp[i * ps[j]] = ps[j];
            if (i % ps[j] == 0) break;
        }
    }
}

int main (void)
{
    int n;

    cin.tie (0)->sync_with_stdio (false);
    cin >> n;

    sieve ();
    memset (f, -1, sizeof f);

    for (int i = 1; i <= n; i++) cin >> w[i];
    for (int i = 1; i <= n; i++) cin >> z[i];
    for (int i = 1; i <= n; i++) if (!vis[i]) {
        int j = i;
        vector<int> q, p;

        while (!vis[j]) vis[j] = true, q.push_back (j), j = w[j];
        int l = q.size (), t = l;
        while (t > 1) {
            int u = minp[t], w = 1;
            while (t % u == 0) t /= u, p.push_back (w *= u);
        }

        int k = -1;
        for (int i = 0; i < l; i++) {
            for (auto j : p) if (f[j] != -1 && i % j != f[j]) goto nxt;
            if (k == -1 || z[q[k]] > z[q[i]]) k = i;
            nxt:;
        }

        for (int i = 0; i < l; i++) res[q[i]] = z[q[(i + k) % l]];
        for (auto v : p) f[v] = k % v;
    }

    for (int i = 1; i <= n; i++) cout << res[i] << " \n"[i == n];
    return 0;
}