自动搬运

查看原文

来自洛谷，原作者为

	CChord **

搬运于2025-08-24 23:13:54，当前版本为作者最后更新于2025-05-30 15:36:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

整体思路

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

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

1. $C$ 内部的逆序对总数。
2. $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;
}