(找规律打表) $O(n)$

最大的数在上一个全排列基础上插入，具体来说公式：
f(i) = f(i-1)*i + (i-1)! * sum[1,i-1]

O(n)

python 代码

N = 1000010
f = [0]*N
Mod = 998244353
a = [0]*N
s = [0]*N
if __name__ == '__main__':
    n = int(input())
    #先预处理前缀和
    for i in range(1,n+1):
        a[i] = i
    for i in range(1,n+1):
        s[i] = (s[i-1] + a[i]) % Mod
    res = 1#计算阶乘
    for i in range(2,n+1):
        res = (res * (i-1)) % Mod
        tem = (res * s[i-1]) % Mod
        f[i] = (f[i-1] * i) % Mod + tem
        f[i] %= Mod

    print(f[n])