第十三届蓝桥杯省赛Java A 组 F 题、Python A 组 G 题、Python B 组 G题——全排列的价值（AC）

太过爱你忘了你带给我的痛 2023-09-28 23:25 16阅读 0赞

#### 目录 ####

*  1.全排列的价值
 *   *  1.题目描述
     *  2.输入格式
     *  3.输出格式
     *  4.样例输入1
     *  5.样例输出2
     *  6.样例输出1
     *  7.样例输出2
     *  8.样例解释
     *  9.原题链接
 *  2.解题思路
 *  3. Ac\_code

## 1.全排列的价值 ##

### 1.题目描述 ###

对于一个排列  A A A= ( a 1 , a 2 , ⋯   , a n ) \\left(a\_\{1\}, a\_\{2\}, \\cdots, a\_\{n\}\\right) (a1,a2,⋯,an), 定义价值  c i c\_\{i\} ci为  a 1 a\_\{1\} a1 至  a i − 1 a\_\{i-1\} ai−1中小于  a i a\_\{i\} ai的数 的个数, 即  c i = ∣ \{ a j ∣ j < i , a j < a i \} ∣ c\_\{i\}=\\mid\\left\\\{a\_\{j\} \\mid j<i, a\_\{j\}<a\_\{i\}\\right\\\} |\_\{\\text \{ \}\} ci=∣\{ aj∣j<i,aj<ai\}∣ 定义  A A A 的价值为  ∑ i = 1 n c i \\sum\_\{i=1\}^\{n\} c\_\{i\} ∑i=1nci。给定  n n n, 求  1 1 1 至  n n n 的全排列中所有排列的价值之和。

### 2.输入格式 ###

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

### 3.输出格式 ###

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

### 4.样例输入1 ###

### 5.样例输出2 ###

2022

### 6.样例输出1 ###

### 7.样例输出2 ###

593300958

### 8.样例解释 ###

1 至 3 构成的所有排列的价值如下:

( 1 , 2 , 3 ) : 0 + 1 + 2 = 3 ( 1 , 3 , 2 ) : 0 + 1 + 1 = 2 ( 2 , 1 , 3 ) : 0 + 0 + 2 = 2 ( 2 , 3 , 1 ) : 0 + 1 + 0 = 1 ( 3 , 1 , 2 ) : 0 + 0 + 1 = 1 ( 3 , 2 , 1 ) : 0 + 0 + 0 = 0 \\begin\{aligned\} &(1,2,3): 0+1+2=3 \\\\ &(1,3,2): 0+1+1=2 \\\\ &(2,1,3): 0+0+2=2 \\\\ &(2,3,1): 0+1+0=1 \\\\ &(3,1,2): 0+0+1=1 \\\\ &(3,2,1): 0+0+0=0 \\end\{aligned\} (1,2,3):0\+1\+2=3(1,3,2):0\+1\+1=2(2,1,3):0\+0\+2=2(2,3,1):0\+1\+0=1(3,1,2):0\+0\+1=1(3,2,1):0\+0\+0=0  
  
故总和为  3 + 2 + 2 + 1 + 1 = 9 3+2+2+1+1=9 3\+2\+2\+1\+1=9 。

### 9.原题链接 ###

[全排列的价值][Link 1]

## 2.解题思路 ##

做过**逆序对**问题的话，明显可以看出对于任意一个排序，其价值等于逆序对的数量。考虑使用`dp`来进行递推，我们定义  f ( n ) f(n) f(n) 为  1 1 1 至  n n n 的全排列中所有排列的价值之和，明显可以得到 f ( 1 ) = 0 ， f ( 2 ) = 1 。 f(1)=0，f(2)=1。 f(1)=0，f(2)=1。

核心问题在于：如何从  f ( n − 1 ) f(n-1) f(n−1) 递推得到  f ( n ) f(n) f(n) 的值？我们以  n n n 为 `4` 时来进行举例，仔细观察  3 3 3 的全排列：  
 ( 1 , 2 , 3 ) ( 1 , 3 , 2 ) ( 2 , 1 , 3 ) ( 2 , 3 , 1 ) ( 3 , 1 , 2 ) ( 3 , 2 , 1 ) \\begin\{aligned\} &(1,2,3) \\\\ &(1,3,2)\\\\ &(2,1,3) \\\\ &(2,3,1) \\\\ &(3,1,2) \\\\ &(3,2,1)\\end\{aligned\} (1,2,3)(1,3,2)(2,1,3)(2,3,1)(3,1,2)(3,2,1)  
此时我们在这些排列的基础上插入`4`，无论在哪个排列中插入`4`，都有`4`个插入的位置， 比如插入第一个排列 ( 1 , 2 , 3 ) (1,2,3) (1,2,3)时可以得到下面这四种情况:  
 ( 4 , 1 , 2 , 3 ) ( 1 , 4 , 2 , 3 ) ( 1 , 2 , 4 , 3 ) ( 1 , 2 , 3 , 4 ) \\begin\{aligned\} &(4,1,2,3) \\\\ &(1,4,2,3)\\\\ &(1,2,4,3) \\\\ &(1,2,3,4) \\end\{aligned\} (4,1,2,3)(1,4,2,3)(1,2,4,3)(1,2,3,4)

我们每个排列只看元素`4`带来的贡献分别为  0 + 1 + 2 + 3 = 6 0+1+2+3=6 0\+1\+2\+3=6，对于`3`的任何一个排列我们插入`4`带来的价值都一样，这是因为我们在  n − 1 n-1 n−1 的全排列插入 n n n时，排列中的元素都严格小于 n n n，所以我们当  n n n 插入的位置之前有几个元素，则带来的价值就是几 。根据该推导可知：当在  n − 1 n-1 n−1的任何一个排列中插入  n n n 时， n n n 带来的贡献则为  ∑ i = 1 n − 1 i \\sum\_\{i=1\}^\{n-1\} i ∑i=1n−1i，也就是从  1 1 1 累加到  n − 1 n-1 n−1，我们可以使用高斯求和计算。当然这只是一个排列带来的价值，对于  n n n 而言，它的全排列的数量为  n ! n ! n!，我们设  g ( n ) g(n) g(n) 为  n n n 的全排列的数量，也就是  n n n 的阶乘。我们上述只考虑了  n n n 给我们带来的价值，我们当然还得考虑其他数，对于排列 ( 1 , 2 , 3 ) (1,2,3) (1,2,3)，在插入`4`后有四种情况，它自己也变成了`4`份，价值也相应变成了`4`倍，`3`的任何一个排列的价值都是如此，由此我们可以得知，当从  f ( n − 1 ) f(n-1) f(n−1) 递推到  f ( n ) f(n) f(n) 时， f ( n − 1 ) f(n-1) f(n−1) 会变成  n n n 倍，根据上述的推导我们可以得到递推转移公式：  
 f ( n ) = f ( n − 1 ) × n + i × ( i − 1 ) 2 × g ( n − 1 ) f(n)=f(n-1)\\times n+ \\frac \{i \\times(i-1)\} \{2\} \\times g(n-1) f(n)=f(n−1)×n\+2i×(i−1)×g(n−1)

当然答案很大，在推导过程中需要进行取模。

## 3. Ac\_code ##

import java.io.*;
    
    public class Main {
        
        static PrintWriter out=new PrintWriter(new OutputStreamWriter(System.out));
        static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        static long[] f=new long[1000010];
        static long[] g=new long[1000010];
        static int MOD=998244353;
        public static void main(String[] args) throws IOException {
        
            int n=Integer.parseInt(br.readLine());
            f[1]=0;
            init(n);
            for (int i = 2; i <=n; i++) {
        
                f[i]=(f[i-1]*i%MOD+(long)i*(i-1)/2%MOD*g[i-1]%MOD)%MOD;
            }
            out.println(f[n]);
            out.flush();
        }
        static void init(int n){
        
            long h=1;
            for (int i = 1; i <=n; i++) {
        
                h*=i;
                h%=MOD;
                g[i]=h;
            }
        }
    }

[Link 1]: https://www.lanqiao.cn/problems/2137/learning/