Dotcpp  >  编程题库  >  蓝桥杯2022年第十三届省赛真题-全排列的价值
题目 2687:

蓝桥杯2022年第十三届省赛真题-全排列的价值

时间限制: 2s 内存限制: 576MB 提交: 3883 解决: 768

题目描述

对于一个排列 A = (a1, a2, · · · , an),定义价值 ci 为 a1 至 ai−1 中小于 ai 的数的个数,即 bi = |{aj | j < i, aj < ai}|。定义 A 的价值为蓝桥杯2022年第十三届省赛真题全排列的价值

给定 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 。 

标签