题解：P12237 [蓝桥杯 2023 国 Java A] 质数排序

· · 题解

整体思路

为表述方便，记：质数下标元素集合为 P，非质数下标元素集合为 C，且元素个数分别为 p，c。

由于 P 已经升序，内部不存在逆序对，因此我们只需要分别求出：

一、C 内部的逆序对

共有 n! 个排列，每个排列中，C 内部有 \frac{c(c-1)}{2} 个数对，每个数对是逆序对的期望为 \frac{1}{2}，因此 C 内部的逆序对总数为：

n!\times\frac{c(c-1)}{2}\times\frac{1}{2}=\frac{c(c-1)n!}{4}

二、C 与 P 之间的逆序对

考虑非质数下标位置 i 的贡献，不妨记该位置前有 k 个质数下标元素，则该位置后有 p-k 个质数下标元素。

考虑 a_i 在集合 \{a_i\} + P 升序排列后所处的位置，显然排在各位置的概率相同，均为 \frac{1}{p+1}，若排在第 j 位 (j=0,1,\cdots,p)，那么 a_i 与 P 中的所有元素形成的逆序对数量为 |j-k|。

因此位置 i 的总贡献为：

\frac{n!}{p+1}\sum_{j=0}^{p}|j-k|=\frac{n!}{p+1}\left(\frac{k(k+1)}{2}+\frac{(p-k)(p-k+1)}{2}\right)

将每个位置 i 的贡献累加即可。

代码实现

#include<bits/stdc++.h>
#define int long long
using namespace std;

constexpr int mod = 998244353;

struct Euler{
    vector<int>primes;
    vector<bool>comp;

    Euler(int n){
        comp.resize(n + 1);
        for(int i = 2; i <= n; i++){
            if(!comp[i]) primes.emplace_back(i);
            for(int j = 0; i * primes[j] <= n; j++){
                comp[i * primes[j]] = true;
                if(!(i % primes[j])) break;
            } 
        }
    }
};

int qmi(int a, int k, int p){
    int res = 1;
    while(k){
        if(k & 1) res = res * a % p;
        a = a * a % p;
        k >>= 1;
    }
    return res;
}

int inv(int a){
    return qmi(a, mod - 2, mod);
}

constexpr int M = 1e6 + 10;
vector<int> fact(M);
void init(){
    fact[0] = 1;
    for(int i = 1; i < M; i++){
        fact[i] = fact[i - 1] * i % mod;
    }
}

void solve(){
    int n; cin >> n;
    Euler sieve(n);
    int p = sieve.primes.size();
    int c = n - p;

    int res = 0;

    int k = 0;
    for(int i = 0; i < n; i++){
        if(i == 0 || sieve.comp[i + 1]){
            res += (k * (k + 1) / 2 + (p - k) * (p - k + 1) / 2) % mod;
            res %= mod;
        }
        else k++;
    }
    res *= fact[n] * inv(p + 1) % mod;
    res %= mod;

    res += c * (c - 1) % mod * inv(4) % mod * fact[n] % mod;
    res %= mod;

    cout << res << '\n';
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    init();
    solve();
    return 0;
}