START201——Permutation Cost Sum（排列成环，交换排序） · znzryb

## 思路讲解

我们发现，即便我们选了一个这个O(1)的，解决简单问题（单组问题的方法），好像也没什么用？所以说问题难道是引导我们怎么直接计算这个东西？我只能说是无从下手呀。

> Cycle decomposition of permutations

这个东西是什么意思那？

[https://nor-blog.pages.dev/posts/2023-01-09-permutations-for-beginners/](https://nor-blog.pages.dev/posts/2023-01-09-permutations-for-beginners/)

其实就是排列成环。

我们发现这个无视距离的交换就非常适合用图论来分析。

最后时间复杂度是 $O(N\sqrt N)$。

```cpp
    FOR(i, 1, N) {
        if (fa[i] == i) {
            ll freq = cnt[i];
            if (freq == 1)
                continue;
            if (memo[freq]) {
                ans += memo[freq];
                ans %= mod;
                continue;
            }
            ll lans = 0;
            // 这里A的定义和题目里面反过来了，不过我认为都一样
            FOR(a, 1, N) {
                ll b = a - a / freq;
                if (b > 1) {
                    // 前面是会变化的 b 来接手
                    lans += (freq) * (1 + b - 1) * (b - 1) / 2;
                    lans %= mod;
                    // 注意 b 的上限是 N
                    // 而不是 a
                    lans += (freq - 1) * (a + a) * (N - b + 1) / 2;
                    lans %= mod;
                } else {
                    lans += (freq - 1) * (a + a) * (N - b + 1) / 2;
                    lans %= mod;
                }
            }
            memo[freq] = lans;
            ans += lans;
            ans %= mod;
        }
    }
```

## AC代码

[https://www.codechef.com/viewsolution/1190700079](https://www.codechef.com/viewsolution/1190700079)



::: 源代码

```cpp
// by Gospel_rock
#include <algorithm>
#include <bits/stdc++.h>
#include <vector>
#define all(vec) vec.begin(), vec.end()
#define PB push_back
#define PF push_front
#define EB emplace_back
#define EF emplace_front
#define EM emplace
#define FI first
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define lson(o) (o << 1)
#define rson(o) (o << 1 | 1)
#define SZ(a) ((long long)a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var << ":" << var << "\n";
#define cend cerr << "\n-----------\n"
#define fsp(x) fixed << setprecision(x)
#define minn(vec) *min_element(vec.begin(), vec.end())
#define maxx(vec) *max_element(vec.begin(), vec.end())

using namespace std;
#ifdef LOCAL
template <typename T> void _print(T x) { cerr << x; }
// 可以打印多层数组，但是格式不是很好
template <typename T> void _print(vector<T> v) {
    cerr << "[ ";
    for (T i : v)
        _print(i), cerr << " ";
    cerr << "]";
}
template <typename T> void _print(set<T> s) {
    cerr << "{ ";
    for (T i : s)
        _print(i), cerr << " ";
    cerr << "}";
}
template <typename T, typename U> void _print(pair<T, U> p) {
    cerr << "{";
    _print(p.first);
    cerr << ", ";
    _print(p.second);
    cerr << "}";
}
template <typename T, typename U> void _print(map<T, U> m) {
    cerr << "{ ";
    for (auto &p : m)
        _print(p), cerr << " ";
    cerr << "}";
}
// 打印两层数组，格式好一些
template <typename T> void _print(vector<vector<T>> v) {
    cerr << "{\n";
    for (auto i : v)
        _print(i), cerr << "\n";
    cerr << " }";
}
#endif

using ll = long long;
using ull = unsigned long long;
using ld = double;
using LD = long double;
using i128 = __int128;
using pdd = pair<ld, ld>;
using plb = pair<ll, bool>;
using pll = pair<ll, ll>;
using vll = vector<ll>;
using vb = vector<bool>;
using tll = tuple<ll, ll, ll>;
using vii = vector<int>;
using vpll = vector<pll>;
using vtll = vector<tll>;
using vdb = vector<ld>;
using vc = vector<char>;
using arr3 = array<ll, 3>;
using arr2 = array<ll, 2>;
using CD = complex<double>;
static constexpr ll MAXN = (ll)2e5 + 10,
                    INF = (ll)1e17 + 3; // 1e17+3是素数 1e18+9是素数
static constexpr ll mod = 998244353;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll N, M, Q, X, K, T, lT;

inline void __();
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> lT;
    while (lT--)
        __();
    return 0;
}
/*

*/
ll fa[MAXN];
ll cnt[MAXN];
ll find(ll x) {
    if (fa[x] == x)
        return x;
    return fa[x] = find(fa[x]);
}
void merge(ll x, ll y) {
    ll fax = find(x), fay = find(y);
    if (fax == fay)
        return;
    fa[fax] = fay;
    cnt[fay] += cnt[fax];
}
inline void __() {
    cin >> N;
    vll P(N + 5);
    // vector<vll> g(N + 5);
    FOR(i, 1, N) {
        fa[i] = i;
        cnt[i] = 1;
    }
    FOR(i, 1, N) {
        cin >> P[i];
        // g[i].PB(P[i]);
        merge(i, P[i]);
    }
    ll ans = 0;
    vll memo(N + 5);
    FOR(i, 1, N) {
        if (fa[i] == i) {
#ifdef LOCAL
            debug(i);
#endif
            ll freq = cnt[i];
#ifdef LOCAL
            debug(freq);
#endif
            if (freq == 1)
                continue;
            if (memo[freq]) {
                ans += memo[freq];
                ans %= mod;
                continue;
            }
            ll lans = 0;
            // 这里A的定义和题目里面反过来了，不过我认为都一样
            FOR(a, 1, N) {
                ll b = a - a / freq;
                if (b > 1) {
                    // 前面是会变化的 b 来接手
                    lans += (freq) * (1 + b - 1) * (b - 1) / 2;
                    lans %= mod;
                    lans += (freq - 1) * (a + a) * (N - b + 1) / 2;
                    lans %= mod;
                } else {
                    lans += (freq - 1) * (a + a) * (N - b + 1) / 2;
                    lans %= mod;
                }
// #ifdef LOCAL
//                 debug(lans);
// #endif
            }
            memo[freq] = lans;
            ans += lans;
            ans %= mod;
        }
    }
    cout << ans << "\n";
}
/*

*/
```


:::


## 心路历程（WA，TLE，MLE……）