jzoj5931. 【NOIP2018模拟10.27】冒泡排序
题目描述
Description
题目背景
冒泡排序的交换次数被定义为交换过程的执行次数。
题面描述
小 S 开始专注于研究⻓度为 n 的排列,他想知道,在你运气足够好的情况下(即每次冒泡排序的交换次数都是可能的最少交换次数,仿佛有上帝之手在操控),对于一个等概率随机的长度为n 的排列,进行这样的冒泡排序的期望交换次数是多少?这tm不是bogo吗
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
题解
根据找规律可以得出,答案怎么找出来的我也不知道
当然我不是这样做的
设f[i]表示当n=i时的答案(方案总数,没有除以n!)
当n=4时,可以列个表得出
排列 --------- 答案
1 2 3 4 ------ 0
1 2 4 3 ------ 1
1 3 2 4 ------ 1
1 3 4 2 ------ 2
1 4 2 3 ------ 2
1 4 3 2 ------ 1
2 1 3 4 ------ 1
2 1 4 3 ------ 2
2 3 1 4 ------ 2
2 3 4 1 ------ 3
2 4 1 3 ------ 3
2 4 3 1 ------ 2
3 1 2 4 ------ 2
3 1 4 2 ------ 3
3 2 1 4 ------ 1
3 2 4 1 ------ 2
3 4 1 2 ------ 2
3 4 2 1 ------ 3
4 1 2 3 ------ 3
4 1 3 2 ------ 2
4 2 1 3 ------ 2
4 2 3 1 ------ 1
4 3 1 2 ------ 3
4 3 2 1 ------ 2
然后就可以发现,当首位不为1时,相同首位的答案-1可以与首位为1的一一对应
于是便有了
问题是怎么证明首位为1的答案+1就是最优解
(为了方便偷懒叙述,下文统一在末尾加数,实质和在队头加数一样)
用s表示结尾为n的方案,则n与s交换后方案为s+1
显然如果直接把n和x交换,那么答案一定是s+1
考虑证明不能用其它方式使答案更优
如果要使答案更优,则n一定不能直接与x交换
这样就只能借助于另一个(或多个)数,设其为y
x不能直接与n交换,考虑借助y来使n回到x的位置上
①y与n交换
y n x=>n y x=>n x y=>y x n
然后就会发现实际上是x和n交换,y没有动过
②y与x交换
y n x=>x n y=>x y n
这个时候有些奇♂妙,因为n回到了原位,且没有与x直接交换
然而可以发现,x的最终位置在y处,所以最后的结果是 y x n,等于x还是和n直接交换了
由此得证,更复杂的情况类似反正都是感性理解
code
#include <iostream>
#include <cstdlib>
#include <cstdio>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define mod 998244353
using namespace std;
long long f[10000001];
long long Jc[10000001];
long long T,i,j,k,l,n,jc;
long long qpower(long long a,int b)
{
long long ans=1;
a%=mod;
while (b)
{
if (b&1) ans=ans*a%mod;
b>>=1;
a=a*a%mod;
}
return ans;
}
int main()
{
freopen("inverse.in","r",stdin);
freopen("inverse.out","w",stdout);
scanf("%lld",&T);
jc=1;Jc[1]=1;
fo(i,2,10000000)
{
f[i]=(i*f[i-1]+jc*(i-1))%mod;
jc=jc*i%mod;
Jc[i]=jc;
}
for (;T;T--)
{
scanf("%lld",&n);
printf("%lld\n",f[n]*qpower(Jc[n],mod-2)%mod);
}
fclose(stdin);
fclose(stdout);
return 0;
}