题解 [ABC371G] Lexicographically Smallest Permutation（中文/English）

· · 题解

本题解提供英文版，位于示例代码之后。

English version of this editorial is provided after the sample code.

官方题解竟然用 Python 来算高精度 lcm，我来提供一个可以避免一切大整数运算的方法。

考察 u\gets P_u 这张图的每个置换环。为了使答案字典序最小，显然需要从前往后贪心地取每个位置。

假设贪心地填完了前 k-1 个元素，第 k 个元素尚未确定取值（这意味着它是所在置换环中编号最小的元素）。找出其所在的置换环，设长度为 len。设最终操作次数为 W，则已经填完的置换环会对 W 的取值做出一些形如 W\equiv R\pmod{Q} 的规定，使用一个数组 req 对所有 Q 记录下对应的 R。枚举当前置换环对 W 取值的限制 W\equiv\Delta\pmod{len}，判断这一限制与已有限制是否有矛盾，在所有没有矛盾的 \Delta 中取使得 A_k 最小化的一个即可。

直接做的复杂度为 O(nd(n))。事实上，我们只需要维护 Q=p^k 的所有限制（其中 p 为质数），可以做到 O(n\log n)。

示例代码 / Sample code:

// Problem: G - Lexicographically Smallest Permutation
// Contest: AtCoder - AtCoder Beginner Contest 371
// URL: https://atcoder.jp/contests/abc371/tasks/abc371_g
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x, y, z) for(int x = (y); x <= (z); ++x)
#define per(x, y, z) for(int x = (y); x >= (z); --x)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do {freopen(s".in", "r", stdin); freopen(s".out", "w", stdout);} while(false)
#define endl '\n'
using namespace std;
typedef long long ll;

mt19937 rnd(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::system_clock::now().time_since_epoch()).count());
int randint(int L, int R) {
    uniform_int_distribution<int> dist(L, R);
    return dist(rnd);
}

template<typename T> void chkmin(T& x, T y) {if(y < x) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}

template<int mod>
inline unsigned int down(unsigned int x) {
    return x >= mod ? x - mod : x;
}

template<int mod>
struct Modint {
    unsigned int x;
    Modint() = default;
    Modint(unsigned int x) : x(x) {}
    friend istream& operator>>(istream& in, Modint& a) {return in >> a.x;}
    friend ostream& operator<<(ostream& out, Modint a) {return out << a.x;}
    friend Modint operator+(Modint a, Modint b) {return down<mod>(a.x + b.x);}
    friend Modint operator-(Modint a, Modint b) {return down<mod>(a.x - b.x + mod);}
    friend Modint operator*(Modint a, Modint b) {return 1ULL * a.x * b.x % mod;}
    friend Modint operator/(Modint a, Modint b) {return a * ~b;}
    friend Modint operator^(Modint a, int b) {Modint ans = 1; for(; b; b >>= 1, a *= a) if(b & 1) ans *= a; return ans;}
    friend Modint operator~(Modint a) {return a ^ (mod - 2);}
    friend Modint operator-(Modint a) {return down<mod>(mod - a.x);}
    friend Modint& operator+=(Modint& a, Modint b) {return a = a + b;}
    friend Modint& operator-=(Modint& a, Modint b) {return a = a - b;}
    friend Modint& operator*=(Modint& a, Modint b) {return a = a * b;}
    friend Modint& operator/=(Modint& a, Modint b) {return a = a / b;}
    friend Modint& operator^=(Modint& a, int b) {return a = a ^ b;}
    friend Modint& operator++(Modint& a) {return a += 1;}
    friend Modint operator++(Modint& a, int) {Modint x = a; a += 1; return x;}
    friend Modint& operator--(Modint& a) {return a -= 1;}
    friend Modint operator--(Modint& a, int) {Modint x = a; a -= 1; return x;}
    friend bool operator==(Modint a, Modint b) {return a.x == b.x;}
    friend bool operator!=(Modint a, Modint b) {return !(a == b);}
};

const int N = 2e5 + 5;

int n, p[N], a[N], vis[N], req[N], ans[N];
vector<int> divs[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n;
    rep(i, 1, n) cin >> p[i];
    rep(i, 1, n) cin >> a[i];
    rep(i, 2, n) {
        if(divs[i].empty()) {
            for(ll d = i; d <= n; d *= i) {
                for(int j = d; j <= n; j += d) {
                    divs[j].push_back(d);
                }
            }
        }
    }
    rep(i, 1, n) req[i] = -1;
    rep(i, 1, n) {
        if(!vis[i]) {
            vector<int> cyc;
            for(int u = i; !vis[u]; u = p[u]) {
                cyc.push_back(u);
                vis[u] = 1;
            }
            // for(int u : cyc) cout << u << " "; cout << endl;
            int len = cyc.size(), steps = -1;
            rep(s, 0, len - 1) {
                bool ok = true;
                for(int d : divs[len]) {
                    if(req[d] != -1 && s % d != req[d]) {
                        ok = false;
                        break;
                    }
                }
                if(ok) {
                    if(steps == -1 || a[cyc[s]] < a[cyc[steps]]) {
                        steps = s;
                    }
                }
            }
            rep(i, 0, len - 1) ans[cyc[i]] = a[cyc[(i + steps) % len]];
            for(int d : divs[len]) req[d] = steps % d;
        }
    }
    rep(i, 1, n) cout << ans[i] << " \n"[i == n];
    return 0;
}

The official solution surprisingly uses Python to compute LCM of big integers. Let me present an algorithm that avoids all big integer computations.

Consider each cycle in the permutation graph u\gets P_u. To make the answer lexicographically smallest, it is obvious that we need to greedily pick each position from left to right.

Suppose the first k-1 elements have been greedily filled, and the value of the k-th element has yet to be determined (which means it is the smallest-indexed element in its cycle). Find the cycle it belongs to and let its length be len. Let the final number of operations be W, and the cycles that have already been filled impose some conditions on W in the form of W\equiv R\pmod{Q}. Use an array req to record the corresponding R for each Q. Enumerate the current cycle's constraint on W, i.e., W\equiv\Delta\pmod{len}, and check if this constraint conflicts with the existing ones. Among all the \Delta that do not conflict, pick the one that minimizes A_k.

The direct approach has a time complexity of O(nd(n)). In fact, we only need to maintain all constraints of Q=p^k (where p is a prime number), which can be done in O(n\log n).