蓝桥杯十三届真题—全排列价值

题目描述

对于一个排列 A = (a1, a2, · · · , an)定义价值$C_i=|a_j|j<i,a_j<a_i|$。定义 A 的价值为${\sum }_{i=1}^n{C}_i$

给定 n求 1 至 n 的全排列中所有排列的价值之和。

输入

输入一行包含一个整数 n 。

输出

输出一行包含一个整数表示答案由于所有排列的价值之和可能很大请输出这个数除以 998244353 的余数。

样例输入

3

样例输出

9

思路

该题目明显要用动态规划进行求解考虑状态转移方程设dp[i]表示1至n的全排列中所有排列价值之和可以发现如下规律

• 考虑全排列生成规律假设已有1到n-1的全排列将n插入到某个排列有n个插入位置则形成1至n的全排列。
• 考虑如何从dp[n-1]生成dp[n]可以将1至n的价值分为两部分n插入前序列的价值+插入n产生的价值
  n插入前的价值每个序列经过插入可构成n个新序列比如12将3插入获得312,132,123。故该部分为$dp[n-1]\ast n$
  插入n产生的价值插入到末尾产生价值为n-1,插入第一个产生价值为0每个位置对应(n-1)!个序列则产生价值为$(n-1)!\ast (0+1+2+\cdots +n-1)=n!(n-1)/2$。
  则状态转移方程应为:$$dp[n]=dp[n-1]\ast n+n!(n-1)/2$$
  考虑到解可能很大边计算边求余,并且用动态规划求阶乘f[i]表示i!对MOD求余的值如下所示
  $$\begin{gathered} f[i]=i\ast f[i-1]\%MOD \\ dp[n]=(dp[n-1]\ast n+f[n]\ast (n-1)/2)\%MOD \end{gathered}$$
  只涉及相邻状态的转换用一个变量表示即可。

代码

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)