列表

详情

NC24672. Bubble Sort

描述

Do you know bubble sort algorithm? It's one of the most famous sorting algorithms.

The bubble sort algorithm is stable, which can be described below:



It's easy for us to find that we need swap  times in the worst case, so the total swapping count is about , where n is the length of the given sequence.

But the above result is an approximate result. As a curious student, Ramen is wondering, among all permutations of length n, what the value of the average exact swap count is?

输入描述

The input contains multiple test cases.

The first line is an integer T(1 <= T <= 10000), which indicates represents the number of test cases.

Each of the next T lines contains an integer n(1 <= n <= 1e18), represents the length of the permutation.

输出描述

For each test case, output the average swap count in one single line.

To avoid possible errors, if the answer is , you need to output , i.e., , where  is the minimum number that suits . 

示例1

输入: 

3
1
3
1000000000000000000

输出: 

0
499122178
178803651

说明:

For n=3, all the permutations and these swap count are:
* [1,2,3] \to 0
* [1,3,2] \to 1
* [2,1,3] \to 1
* [2,3,1] \to 2
* [3,1,2] \to 2
* [3,2,1] \to 3
So the answer is \displaystyle{\frac{0+1+1+2+2+3}{6}}\equiv9\times6^{-1}\equiv499122178 \pmod{998244353}.

原站题解

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

C++(g++ 7.5.0) 解法, 执行用时: 35ms, 内存消耗: 512K, 提交时间: 2023-04-21 20:22:44 

#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
const int mod=998244353;
int T;
ll n;
ll qmi(ll x,ll b)
{
	ll res=1;
	while(b)
	{
		if(b&1)res=res*x%mod;
		x=x*x%mod;
		b>>=1;
	}
	return res;
}
int work(ll x)
{
	ll res=x*(x-1)%mod;
	ll k=qmi(4,mod-2);
	res=res*k%mod;
	return res;
}
int main(){
	
	cin>>T;
	while(T--)
	{
		cin>>n;
		n%=mod;
		cout<<work(n)<<endl;
	}
	return 0;
	
}

C++14(g++5.4) 解法, 执行用时: 27ms, 内存消耗: 504K, 提交时间: 2019-04-14 22:11:44 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
int main(){
    int t;
    cin>>t;
    while(t--){
        ll x;
        cin>>x;
        cout<<x%mod*(x%mod-1+mod)%mod*748683265%mod<<endl;
    }
}

C++11(clang++ 3.9) 解法, 执行用时: 38ms, 内存消耗: 764K, 提交时间: 2020-02-26 21:57:32 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		ll x;
		cin>>x;
		cout<<x%mod*(x%mod-1+mod)%mod*748683265%mod<<endl;
	}
}

上一题

© 2024 nowcoder.com