可以采用dp的思想
例如 n=3
(1,2,3) (1,3,2) (2,1,3) (2,3,1) (3,1,2) (3,2,1)
假设4要插入,每个都有四个位置可以插入,价值分别为0 1 2 3 这四个位置
所以代码为
n=int(input())
mod=998244353
res=1
dp=1
ans=2
for i in range(3,n+1):
res=(res+(i-1))%mod #记录i能插入所有位置能增加多少总价值
dp=(dp*i+(ans*res))%mod #(dp乘以i)表示i插入后,原来的价值由于数量所扩大的价值。
#(ans乘以res)表示i插入后,i所增加的总价值
ans=(ans*i)%mod #记录i的排列数
print(dp)
插入一个公式
bn=bn−1∗n+An−1n−1∗Sn−1
其中Sn−1是前n−1项的和An−1n−1为n−1的全排列数bn为总价值