2052: [蓝桥杯2022初赛] 全排列的价值

内存限制:256 MB 时间限制:1 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:372 通过:96

题目描述

对于一个排列A = (a[1], a[2], ... , a[n]),定义价值c[i] 为a[1]至a[i-1]中小于a[i]的数的个数。
即c[i] = |{a[j] |j < i, a[j] < a[i]}|。定义A的价值为Sum(c[1]+c[2]+...+c[n])。
给定n,求1至n的全排列中所有排列的价值之和。

输入格式

输入一行包含一个整数n。
对于40%的评测用例,n≤20;
对于70%的评测用例,n5000;
对于所有评测用例,2n1000000。

输出格式

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

输入样例 复制

样例1:
3

样例2:
2022

输出样例 复制

样例1:
9

样例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。