MoonLight的冒泡排序难题

NC252716. MoonLight的冒泡排序难题

描述

Moonlight 最近迷上了冒泡排序。今天，他想动手试一试。

于是，氧气少年给了 MoonLight 一个长度为 $n(1\leq n\leq 2\cdot 10^5)$ 的排列 $p$ ，好让他练练手。

MoonLight 会不停地进行下面的操作，直到当前排列变成严格递增的排列：

选择一个最大的、不满足 $p_i=i$ 的元素 $p_i$ ，然后将其向后移动到位置 $p_i$ ，其他元素保持原来的顺序不变。

上述过程可以用下面的伪代码表示：
$\boxed<br />{<br /> \begin {split}<br /> & \mathbf{while}\ \ p\ \text{is not in increasing order}\ \ \mathbf{do}\\<br /> & \quad\quad pos\leftarrow \text{the index of the maximum }p_i\text{ that satisfies }p_i\neq i\\<br /> & \quad\quad val\leftarrow \text{the value of the maximum }p_i\text{ that satisfies }p_i\neq i\\<br /> & \quad\quad \mathbf{for}\ \ i\ \ \text{from}\ \ pos\ \ \text{to}\ \ val-1\ \ \mathbf{do} \\<br /> & \quad \quad \quad\quad \text{Swap}\ \ p_i\ \text{with}\ p_{i+1} \\<br /> & \quad\quad\mathbf{end\ for} \\<br /> & \mathbf{end\ while} \\<br /> \end {split}<br />}$

现在，氧气少年不小心打乱了这个排列，每种排列出现的概率均等。

MoonLight 想知道，操作进行的轮数（也就是伪代码中 $\text{while}$ 循环进行的轮数）的期望值。

可以证明，答案可以表示成 $\frac{p}{q}$ 的形式。其中， $p\geq 0,q\geq 1,\gcd(p,q)=1,q\mod 998244353\neq 0$ 。因此你只需输出 $p\cdot q^{998244351}\mod 998244353$ 即可。

输入描述

第一行包含一个整数 ，表示测试用例的组数。

对于每组测试用例：

仅输入一行，包含一个整数 ，表示排列  的长度。

输出描述

对于每组测试用例：

仅输出一行，包含一个整数，表示答案。

示例1

输入:

输出:

0
499122177
166374060

说明:

对于第一组测试用例：

当 $n=1$ 时，排列 $p$ 只有一种可能： $[1]$ ，操作进行的轮数只可能是 $0$ 。

对于第二组测试用例：

当 $n=2$ 时，排列 $p$ 有两种可能： $[1,2]\ [2,1]$ ，这两种情况出现的概率均为 $\frac{1}{2}$ ，操作进行的轮数分别是 $0,1$ 。期望为 $\frac{1}{2}\cdot 0+\frac{1}{2}\cdot 1=\frac{1}{2}$ 。 $1\cdot 2^{998244351} \mod 998244353=499122177$ 。

上次编辑到这里，代码来自缓存点击恢复默认模板

C++(g++ 7.5.0) 解法, 执行用时: 82ms, 内存消耗: 5052K, 提交时间: 2023-05-28 20:01:24

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mxn=2e5+10,mod = 998244353;
ll t,n,dp[mxn];
ll quickfirst(ll a,ll b){
	ll res=1;
	while(b){
		if(b&1) res=res*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return res;
}
int main(){
	dp[1]=0;
	for(int i=2;i<=2e5;i++){
		dp[i]=(dp[i-1]+(i-1)*quickfirst(i,mod-2)%mod)%mod;
	}
	scanf("%lld",&t);
	while(t--){
		scanf("%lld",&n);
		printf("%lld\n",dp[n]);
	}
	return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 580ms, 内存消耗: 3912K, 提交时间: 2023-05-27 13:08:20

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int mod=998244353;
ll f[200005];
ll qmi(ll a,ll b,ll p){
	ll res=1%p;
	while(b){
		if(b&1)res=res*a%p;
		a=a*a%p;
		b>>=1;
	}
	return res;
} 
int main()
{
    for(ll i=1;i<=200000;i++){
        f[i]=(f[i-1]+(i-1)*qmi(i,mod-2,mod))%mod;
    }
    ll t;
    cin>>t;
    while(t--){
        ll n;cin>>n;
        cout<<f[n]<<endl;
    }
}

Python3 解法, 执行用时: 1830ms, 内存消耗: 22424K, 提交时间: 2023-05-27 21:04:20

mod = 998244353
N = int(200000)
e = 1
h = [0]*(N+3)
inv = [0]*(N+3)
for i in range(1,N+1):
    h[i] = i*h[i-1]+(i-1)*e
    h[i] %=mod
    e = e * i % mod
inv[N] = pow(e,mod-2,mod)

for i in range(N-1,-1,-1):
	inv[i] = inv[i+1]*(i+1)%mod
     

for i in range(int(input())):
    n = int(input())
    print(h[n]*inv[n]%mod)

pypy3 解法, 执行用时: 1146ms, 内存消耗: 28332K, 提交时间: 2023-05-27 12:29:06

T=int(input())
MOD=998244353
res=[0]
ret=0
for i in range(2*int(1e5)+10):
    ret = (ret + i * pow(i + 1, MOD - 2, MOD) % MOD) % MOD
    res.append(ret)
while T:
    n=int(input())
    print(res[n])
    T-=1