题目 2687:
蓝桥杯2022年第十三届省赛真题-全排列的价值
时间限制: 2s
内存限制: 576MB 提交: 3901 解决: 770
题目描述
对于一个排列 A = (a1, a2, · · · , an)，定义价值 ci 为 a1 至 ai−1 中小于 ai 的数的个数，即 bi = |{aj | j < i, aj < ai}|。定义 A 的价值为
。
给定 n，求 1 至 n 的全排列中所有排列的价值之和。
输入格式
输入一行包含一个整数 n 。
输出格式
输出一行包含一个整数表示答案，由于所有排列的价值之和可能很大，请输出这个数除以 998244353 的余数。
样例输入
3
样例输出
9
提示
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 ≤ 106 。