题目描述
对于一个排列 A = (a1, a2, · · · , an)，定义价值 C i = ∣ a j ∣ j < i , a j < a i ∣ C_i = |{a_j | j < i, a_j < a_i}| Ci=∣aj∣j<i,aj<ai∣。定义 A 的价值为 ∑ i = 1 n C i \sum_{i=1}^nC_i ∑i=1nCi
给定 n，求 1 至 n 的全排列中所有排列的价值之和。
输入
输入一行包含一个整数 n 。
输出
输出一行包含一个整数表示答案，由于所有排列的价值之和可能很大，请输出这个数除以 998244353 的余数。
样例输入
3
样例输出
9文章来源：https://www.toymoban.com/news/detail-411907.html
思路
该题目明显要用动态规划进行求解，考虑状态转移方程，设dp[i]表示1至n的全排列中所有排列价值之和，可以发现如下规律：文章来源地址https://www.toymoban.com/news/detail-411907.html
- 考虑全排列生成规律，假设已有1到n-1的全排列，将n插入到某个排列（有n个插入位置）则形成1至n的全排列。
- 考虑如何从dp[n-1]生成dp[n]，可以将1至n的价值分为两部分：n插入前序列的价值+插入n产生的价值
n插入前的价值：每个序列经过插入可构成n个新序列，比如12，将3插入获得312,132,123。故该部分为： d p [ n − 1 ] ∗ n dp[n-1]*n dp[n−1]∗n
插入n产生的价值：插入到末尾产生价值为n-1,插入第一个产生价值为0，每个位置对应(n-1)!个序列，则产生价值为 ( n − 1 ) ! ∗ ( 0 + 1 + 2 + ⋯ + n − 1 ) = n ! ( n − 1 ) / 2 (n-1)!*(0+1+2+\cdots +n-1)=n!(n-1)/2 (n−1)!∗(0+1+2+⋯+n−1)=n!(n−1)/2。
则状态转移方程应为: d p [ n ] = d p [ n − 1 ] ∗ n + n ! ( n − 1 ) / 2 dp[n]=dp[n-1]*n+n!(n-1)/2 dp[n]=dp[n−1]∗n+n!(n−1)/2
考虑到解可能很大，边计算边求余,并且用动态规划求阶乘，f[i]表示i!对MOD求余的值，如下所示：
f [ i ] = i ∗ f [ i − 1 ] % M O D d p [ n ] = ( d p [ n − 1 ] ∗ n + f [ n ] ∗ ( n − 1 ) / 2 ) % M O D f[i]=i*f[i-1]\%MOD\\dp[n]=(dp[n-1]*n+f[n]*(n-1)/2)\%MOD f[i]=i∗f[i−1]%MODdp[n]=(dp[n−1]∗n+f[n]∗(n−1)/2)%MOD
只涉及相邻状态的转换，用一个变量表示即可。
代码
MOD = 998244353
n = int(input().strip())
dp = 0
f = 1
for i in range(2,n+1):
dp = (dp*i+f*i*(i-1)//2)%MOD
f = f*i%MOD
print(dp)
到了这里，关于蓝桥杯十三届真题—全排列价值的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
