打卡信奥刷题（2170）用C++实现信奥 P12369 [蓝桥杯 2022 省 Python B] 全排列的价值

rogeliu

1086人浏览 · 2025-10-06 13:09:31

rogeliu · 2025-10-06 13:09:31 发布

P12369 [蓝桥杯 2022 省 Python B] 全排列的价值

题目描述

对于一个排列 $,an)A=(a_1,a_2,\cdots,a_n)$ ，定义价值 $c_i$ 为 $a_1$ 至 $a_{i-1}$ 中小于 $a_i$ 的数的个数，即 $c_i=|\{a_j|j<i,a_j<a_i\}|$ 。定义 $A$ 的价值为 $∑i=1nci\displaystyle \sum_{i=1}^{n}c_i$ 。

给定 $n$ ，求 $1$ 至 $n$ 的全排列中所有排列的价值之和。

输入格式

输入一行包含一个整数 $n$ 。

输出格式

输出一行包含一个整数表示答案，由于所有排列的价值之和可能很大，请输出这个数除以 $998244353$ 的余数。

输入输出样例 #1

输入 #1

输出 #1

输入输出样例 #2

输入 #2

输出 #2

593300958

说明/提示

样例说明

$1$ 至 $3$ 构成的所有排列的价值如下:

$(1,2,3):0+1+2=3(1,3,2):0+1+1=2(2,1,3):0+0+2=2(2,3,1):0+1+0=1(3,1,2):0+0+1=1(3,2,1):0+0+0=0\begin{aligned}& (1,2,3): 0+1+2=3 \\& (1,3,2): 0+1+1=2 \\& (2,1,3): 0+0+2=2 \\& (2,3,1): 0+1+0=1 \\& (3,1,2): 0+0+1=1 \\& (3,2,1): 0+0+0=0\end{aligned}$

故总和为 $3 + 2 + 2 + 1 + 1 = 9$ 。

评测用例规模与约定

对于 $40%40\%$ 的评测用例， $\leq 20$ ；
对于 $70%70\%$ 的评测用例， $\leq 5000$ ；
对于所有评测用例， $\leq n \leq 10^6$ 。

C++实现

#include<bits/stdc++.h>
#define int long long
#define _ 0
using namespace std;
const int N = 1e6 + 10, mod = 998244353;
int n;
int fac[N];//阶乘 
int qp(int a, int b, int p)//快速幂 
{
	int res = 1;
	while(b)
	{
		if(b & 1) res = res * a % p;
		a = a * a % p;
		b >>= 1;
	}
	return res;
}
void initfac()//预处理阶乘 
{
	fac[0] = 1;
	for(int i = 1; i < N; i ++)
		fac[i] = fac[i - 1] * i % mod;
}
signed main()
{
	initfac();
	cin >> n;
	cout << fac[n] * n % mod * (n - 1) % mod * qp(4ll, mod - 2, mod) % mod;
	return (0^_^0);
}