JZOJ-senior-5931. 【NOIP2018模拟10.27】冒泡排序

Time Limits: 1000 ms Memory Limits: 262144 KB

Description

冒泡排序的交换次数被定义为交换过程的执行次数。

小 S 开始专注于研究⻓度为 n 的排列，他想知道，在你运气足够好的情况下（即每次冒泡排序的交换次数都是可能的最少交换次数，仿佛有上帝之手在操控），对于一个等概率随机的长度为n 的排列，进行这样的冒泡排序的期望交换次数是多少？

Input

从文件 inverse.in 中读入数据。
输入第一行包含一个正整数 T ，表示数据组数。
对于每组数据，第一行有一个正整数，保证 n ≤ 10^7 。

Output

输出到文件 inverse.out 中。
输出共 T 行，每行一个整数。
对于每组数据，输出一个整数，表示答案对 998244353 取模的结果。

Sample Input

2
2
4

样例 2
见选手目录下的 inverse/inverse2.in 与 inverse/inverse2.ans 。

Sample Output

499122177
415935149

Data Constraint

Solution

• 看错题……找不到规律真是令人心态崩了
• 题目大意是对于一个 $n$n 的排列，它的贡献就是将它交换有序的最少次数，求所有排列的期望次数
• 实在想不出来不妨找规律，如Code1&Code2（求逆元方式不同）
• 找规律的方法我太菜不会证明，那就讲另一种方法吧（Code3）
• 设 $f_i$fi​ 表示前 $i$i 个数的期望次数，考虑将第 $i$i 个数放到哪个位置
• 直接放在第 $i$i 位，无需交换，直接加上 $f_{i-1}$fi−1​
• 不放在第 $i$i 位，那么它有 $i-1$i−1 种放法，另外 $i-1$i−1 个数有 $(i-1)!$(i−1)! 种方案
• 所以一共有 $(i-1)*(i-1)!$(i−1)∗(i−1)! 种方案贡献为 $1$1 ，此外，另外 $i-1$i−1 个数也要交换，产生贡献 $(i-1)*f_{i-1}$(i−1)∗fi−1​
• （感觉思想上和错排公式的推导差不多）
• 于是得到递推式 $f_i=i*f_{i-1}+(i-1)*(i-1)!$fi​=i∗fi−1​+(i−1)∗(i−1)!
• 预处理一下就好了

线性求逆元

Code 1

#include<algorithm>
#include<cstdio>

#define fo(i,a,b) for(int i=a;i<=b;++i)
#define fd(i,a,b) for(int i=a;i>=b;--i)
#define ll long long

using namespace std;

const ll N=1e7,P=998244353;
ll T,n,ny[N+5],sum[N+5];

ll ksm(ll a,ll b)
{
	ll s=1;
	for(;b;a=a*a%P,b>>=1)
		if(b&1) s=s*a%P;
	return s;
}

int main()
{
	freopen("inverse.in","r",stdin);
	freopen("inverse.out","w",stdout);
	ny[0]=ny[1]=sum[1]=1;
	fo(i,2,N)
	{
		ny[i]=P-(P/i)*ny[P%i]%P;//线性求逆元
		sum[i]=(sum[i-1]+ny[i])%P;
	}
	scanf("%lld",&T);
	while(T--)
	{
		scanf("%lld",&n);
		ll ans=((n-sum[n])%P+P)%P;
		printf("%lld\n",ans);
	}
}

Code 2

copy from ZZ

#include<cstdio>
#include<cstring>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define N 10000010
#define mo 998244353
#define m 10000000
#define ll long long
using namespace std;
int n,jc[N],f[N],ny[N];
ll ans=0;
ll mi(ll a,ll b)
{
	ll c=1;
	for(;b;b/=2,a=a*a%mo) if(b%2==1) c=c*a%mo;
	return c;
}
int main()
{
	freopen("inverse.in","r",stdin);
	freopen("inverse.out","w",stdout);
	int ac;scanf("%d",&ac);
	jc[0]=1;fo(i,1,m) jc[i]=1ll*jc[i-1]*i%mo;
	ny[m]=mi(jc[m],mo-2);
	fd(i,m-1,1) ny[i]=1ll*ny[i+1]*(i+1)%mo;
	fo(i,1,m) 
	f[i]=(f[i-1]+1ll*ny[i]*jc[i-1]%mo)%mo;//差分求逆元
	while(ac--)
	{
		scanf("%d",&n);
		printf("%d\n",(n-f[n]+mo)%mo);
	}
}

Code 3

copy from LZH

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define fo(i,j,k) for(int i=j;i<=k;++i)
#define fd(i,j,k) for(int i=j;i>=k;--i)
using namespace std;
typedef long long ll;
const int N=1e7+10,mo=998244353;
ll ny[N],f[N];
ll pow(ll x,int y){
	ll s=1;
	for(;y;y>>=1,x=x*x%mo) if(y&1) s=s*x%mo;
	return s;
}
int main()
{
	freopen("inverse.in","r",stdin);
	freopen("inverse.out","w",stdout);
	ll s=1;
	f[1]=0;
	fo(i,2,N-10){
		f[i]=(f[i-1]*i%mo+s*(i-1)%mo)%mo;
		s=s*i%mo;
	}
	ny[N-10]=pow(s,mo-2);
	fd(i,N-11,0) ny[i]=ny[i+1]*(i+1)%mo;
	fo(i,1,N-10) f[i]=f[i]*ny[i]%mo;
	int T;
	scanf("%d",&T);
	while(T--){
		int n;
		scanf("%d",&n);
		printf("%lld\n",f[n]);
	}
}