全排列的价值（JAVA）

题目：

对于一个排列 A=(a1,a2,⋯,an), 定义价值ci 为a1 至ai−1 中小于ai 的数的个数, 即ci=∣{aj∣j<i,aj<ai}∣。

定义 A 的价值为 c_{i}∑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=93+2+2+1+1=9 。

评测用例规模与约定
对于 40% 的评测用例, n≤20;

对于 70% 的评测用例, n≤5000;

对于所有评测用例, 2≤n≤106 。

运行限制
最大运行时间：1s
最大运行内存: 512M

代码：

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
 
public class Main {
       public static void main(String[] args) {
                Scanner scan = new Scanner(System.in);
                int n= scan.nextInt();
                long num=1;             
                long sum=1;
                long []dp=new long[n+1];
                dp[0]=0;
                dp[1]=0;
                for (int i = 2; i <=n ; i++) {
                    dp[i]=(dp[i-1]*(i)+num*sum)%998244353;
                    sum=(sum+i)%998244353;
                    num=(num*i)%998244353;
                }
                System.out.println(dp[n]);
                scan.close();
            }
        }