问题描述
对于一个排列 A=(a1,a2,⋯,an), 定义价值 ci 为 a1 至 ai−1 中小于 ai 的数 的个数, 即 。
ci=∣{aj∣j<i,aj<ai}∣。
定义 A 的价值为 ∑i=1nci 。
给定 n, 求 1 至 n 的全排列中所有排列的价值之和。
输入格式
输入一行包含一个整数 n 。
输出格式
输出一行包含一个整数表示答案, 由于所有排列的价值之和可能很大, 请 输出这个数除以 998244353 的余数。
样例输入 1
3
样例输出 1
9
样例输入 2
2022
样例输出 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
故总和为 3+2+2+1+1=9。
评测用例规模与约定
对于 40% 的评测用例, n ≤ 20;
对于 70% 的评测用例, n ≤ 5000;
对于所有评测用例, 2 ≤ n ≤ 10^6 。
运行限制
- 最大运行时间：1s
- 最大运行内存: 512M
思路：
参考代码：
a=998244353
n=int(input())
ans=n*(n-1)//2%a
for i in range(3,n+1):
ans=ans*i%a
print(ans)
