【JZOJ A组】冒泡排序

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

思路

我们把这个数的位置与它的排名的位置连边，于是他们就会构成许多环
可以发现，一个环交换次数为环的大小-1，所以我们需要尽可能多的环

问题就转换成期望亦多少个环

可以发现只有自己连自己，环的数量才会增加，所以加入第i个点形成换的概率是1/i，所以答案就是n-sigma（1/i）(1<=i<=n)

代码

#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define ll long long
using namespace std;
const int N=5e4+77,M=5e4+77;
struct ahah
{
	ll L,R,p,f;
}ask[N];
struct haha
{
	ll x,y;
}ans[N];
ll answer,n,m,q,a[N],cnt[N],k;
ll gcd(ll a,ll b)
{
	return !b?a:gcd(b,a%b);
}
bool comp(ahah a,ahah b)
{
	return a.L/k==b.L/k?a.R<b.R:a.L<b.L;
}
void remove(ll pos)
{
	if(--cnt[a[pos]]>0)answer+=(-2)*(cnt[a[pos]]);}
void add(ll pos){ if(++cnt[a[pos]]>1)answer+=2*(cnt[a[pos]]-1); }
void work(ll x,ll y,ll p)
{
	if(!x)ans[p].x=0,ans[p].y=1;
	else 
	{
		ll k=gcd(x,y);
		ans[p].x=x/k;
		ans[p].y=y/k;
	}
}
int main()
{
	scanf("%lld%lld",&n,&q);
	k=sqrt(n);
	for(int i=1; i<=n; i++)scanf("%lld",&a[i]);
	for(int i=1; i<=q; i++)scanf("%lld%lld",&ask[i].L,&ask[i].R),ask[i].p=i;
	sort(ask+1,ask+1+q,comp);
	ll curl=0,curr=0;
	for(int i=1; i<=q; i++)
	{
		ll L=ask[i].L,R=ask[i].R;
		if(L==R)
		{
			ans[ask[i].p].x=0;
			ans[ask[i].p].y=1;
			continue;
		}
		while(curl<L)remove(curl++);
		while(curl>L)add(--curl);
		while(curr<R)add(++curr);
		while(curr>R)remove(curr--);
		work(answer,(R-L+1)*(R-L),ask[i].p);
	}
	for(int i=1; i<=q; i++)printf("%lld/%lld\n",ans[i].x,ans[i].y);
}