- 有点DP的感觉
- 令f[i]表示i的全排列价值之和
- 考虑具体方案的构成,当i-1排列已经计算完毕,增加i时,i插入的位置有i
种
- 如果插在所有i-1
排列的最前面的状态,价值等于 f[i-1] (相当于i不贡献价值)
- 如果插在所有i-1
排列第一个数后面的状态,价值等于 f[i-1]+(i-1)!1
(每个排列增加1
的贡献)
- 如果插在所有i-1
排列第二个数后面状态,价值等于 f[i-1]+(i-1)!2
(每个排列增加2
的贡献)
- ……
- 如果插在所有i-1排列最后一个数后面状态,价值等于 f[i-1]+(i-1)!(i-1)
(每个排列增加i-1
的贡献)
- 又一共由i种插入方式,故 f[i-1]i
- 此处为什么是 贡献值*阶乘:因为1~(i-1)一共有(i-1)!种排列方式,每一种排列方式都整加了相同贡献值
- 所以f[i]=f[i-1]*i+fact[i-1]*sum[i-1]
- 其中fact[i]表示i阶乘,sum[i]表示1+2+…+i
n = int(input())
mod = 998244353
f = [0] * (n + 1) # 价值数组
fact = [0 for _ in range(n + 1)] # 阶乘数组
sum = [0 for _ in range(n + 1)] # 前缀和数组
f[0], f[1] = 0, 0
# 预处理阶乘数组:
for i in range(2, n + 1):
fact[1] = 1
fact[i] = fact[i - 1] * i
fact[i] %= mod
# 预处理前缀和数组:
for i in range(2, n + 1):
sum[1] = 1
sum[i] = sum[i - 1] + i
sum[i] %= mod
# 按照递推公式求f[i]
for i in range(2, n + 1):
f[i] = f[i - 1] * i + fact[i - 1] * sum[i - 1]
f[i] %= mod
print(f[n])