Partial Sorting

题意翻译

### 题目描述 给定整数 $n$ 和质数 $M$。 对于一个 $1\sim 3n$ 的排列 $p$，你可以进行下列操作： - 将 $p$ 的前 $2n$ 个元素从小到大排序。 - 将 $p$ 的后 $2n$ 个元素从小到大排序。 可以证明任意 $1\sim 3n$ 的排列都能通过若干次上述操作从小到大排序。 记 $f(p)$ 表示将 $p$ 从小到大排序所需的最小总操作次数。 你需要求出对于所有 $1\sim 3n$ 的排列 $p$，其 $f(p)$ 总和对 $M$ 取模后的值。 ### 输入格式 输入一行两个整数 $n,M(1\leq n\leq10^6;10^8\leq M\leq10^9)$，保证 $M$ 是质数。 ### 输出格式 输出一行一个整数表示 $f(p)$ 的总和对 $M$ 取模后的值。

题目描述

Consider a permutation $ ^\dagger $ $ p $ of length $ 3n $ . Each time you can do one of the following operations: - Sort the first $ 2n $ elements in increasing order. - Sort the last $ 2n $ elements in increasing order. We can show that every permutation can be made sorted in increasing order using only these operations. Let's call $ f(p) $ the minimum number of these operations needed to make the permutation $ p $ sorted in increasing order. Given $ n $ , find the sum of $ f(p) $ over all $ (3n)! $ permutations $ p $ of size $ 3n $ . Since the answer could be very large, output it modulo a prime $ M $ . $ ^\dagger $ A permutation of length $ n $ is an array consisting of $ n $ distinct integers from $ 1 $ to $ n $ in arbitrary order. For example, $ [2,3,1,5,4] $ is a permutation, but $ [1,2,2] $ is not a permutation ( $ 2 $ appears twice in the array), and $ [1,3,4] $ is also not a permutation ( $ n=3 $ but there is $ 4 $ in the array).

输入输出格式

输入格式

The only line of input contains two numbers $ n $ and $ M $ ( $ 1 \leq n \leq 10^6 $ , $ 10^8 \leq M \leq 10^9 $ ). It is guaranteed that $ M $ is a prime number.

输出格式

Output the answer modulo $ M $ .

输入输出样例

输入样例 #1

1 100009067

输出样例 #1

9

输入样例 #2

2 100000357

输出样例 #2

1689

输入样例 #3

69 999900997

输出样例 #3

193862705

说明

In the first test case, all the permutations are: - $ [1, 2, 3] $ , which requires $ 0 $ operations; - $ [1, 3, 2] $ , which requires $ 1 $ operation; - $ [2, 1, 3] $ , which requires $ 1 $ operation; - $ [2, 3, 1] $ , which requires $ 2 $ operations; - $ [3, 1, 2] $ , which requires $ 2 $ operations; - $ [3, 2, 1] $ , which requires $ 3 $ operations. Therefore, the answer is $ 0+1+1+2+2+3=9 $ .

**部分排序**

**题目描述：**
给定整数 $ n $ 和质数 $ M $。对于一个长度为 $ 3n $ 的排列 $ p $，你可以进行以下操作：

- 将排列的前 $ 2n $ 个元素从小到大排序。
- 将排列的后 $ 2n $ 个元素从小到大排序。

可以证明，任何长度为 $ 3n $ 的排列都可以通过上述操作从小到大排序。定义 $ f(p) $ 为将排列 $ p $ 从小到大排序所需的最小操作次数。你需要计算对于所有长度为 $ 3n $ 的排列 $ p $，$ f(p) $ 的总和，并将结果对 $ M $ 取模。

**输入格式：**
输入包含一行两个整数 $ n, M $（$ 1 \leq n \leq 10^6 $；$ 10^8 \leq M \leq 10^9 $），保证 $ M $ 是质数。

**输出格式：**
输出一行一个整数，表示 $ f(p) $ 的总和对 $ M $ 取模后的值。

**题目描述：**
考虑一个长度为 $ 3n $ 的排列 $ p $。每次你可以执行以下操作之一：

- 将前 $ 2n $ 个元素按升序排序。
- 将后 $ 2n $ 个元素按升序排序。

我们可以证明，任何排列都可以仅使用这些操作按升序排序。定义 $ f(p) $ 为将排列 $ p $ 按升序排序所需的最小操作次数。

给定 $ n $，找出所有 $ (3n)! $ 长度的排列 $ p $ 的 $ f(p) $ 之和。

由于答案可能非常大，以模质数 $ M $ 的形式输出结果。

**输入输出格式：**
**输入格式：**
输入仅包含一行，包含两个数字 $ n $ 和 $ M $（$ 1 \leq n \leq 10^6 $，$ 10^8 \leq M \leq 10^9 $）。保证 $ M $ 是一个质数。

**输出格式：**
以模 $ M $ 的形式输出答案。

**输入输出样例：**
**输入样例 #1：**
```
1 100009067
```
**输出样例 #1：**
```
9
```
**输入样例 #2：**
```
2 100000357
```
**输出样例 #2：**
```
1689
```
**输入样例 #3：**
```
69 999900997
```
**输出样例 #3：**
```
193862705
```

**说明：**
在第一个测试案例中，所有排列如下：

- $ [1, 2, 3] $，需要 $ 0 $ 次操作；
- $ [1, 3, 2] $，需要 $ 1 $ 次操作；
- $ [2, 1, 3] $，需要 $ 1 $ 次操作；
- $ [2, 3, 1] $，需要 $ 2 $ 次操作；
- $ [3, 1, 2] $，需要 $ 2 $ 次操作；
- $ [3, 2, 1] $，需要 $ 3 $ 次操作。

因此，答案为 $ 0+1+1+2+2+3=9 $。**部分排序** **题目描述：** 给定整数 $ n $ 和质数 $ M $。对于一个长度为 $ 3n $ 的排列 $ p $，你可以进行以下操作： - 将排列的前 $ 2n $ 个元素从小到大排序。 - 将排列的后 $ 2n $ 个元素从小到大排序。 可以证明，任何长度为 $ 3n $ 的排列都可以通过上述操作从小到大排序。定义 $ f(p) $ 为将排列 $ p $ 从小到大排序所需的最小操作次数。你需要计算对于所有长度为 $ 3n $ 的排列 $ p $，$ f(p) $ 的总和，并将结果对 $ M $ 取模。 **输入格式：** 输入包含一行两个整数 $ n, M $（$ 1 \leq n \leq 10^6 $；$ 10^8 \leq M \leq 10^9 $），保证 $ M $ 是质数。 **输出格式：** 输出一行一个整数，表示 $ f(p) $ 的总和对 $ M $ 取模后的值。 **题目描述：** 考虑一个长度为 $ 3n $ 的排列 $ p $。每次你可以执行以下操作之一： - 将前 $ 2n $ 个元素按升序排序。 - 将后 $ 2n $ 个元素按升序排序。 我们可以证明，任何排列都可以仅使用这些操作按升序排序。定义 $ f(p) $ 为将排列 $ p $ 按升序排序所需的最小操作次数。 给定 $ n $，找出所有 $ (3n)! $ 长度的排列 $ p $ 的 $ f(p) $ 之和。 由于答案可能非常大，以模质数 $ M $ 的形式输出结果。 **输入输出格式：** **输入格式：** 输入仅包含一行，包含两个数字 $ n $ 和 $ M $（$ 1 \leq n \leq 10^6 $，$ 10^8 \leq M \leq 10^9 $）。保证 $ M $ 是一个质数。 **输出格式：** 以模 $ M $ 的形式输出答案。 **输入输出样例：** **输入样例 #1：** ``` 1 100009067 ``` **输出样例 #1：** ``` 9 ``` **输入样例 #2：** ``` 2 100000357 ``` **输出样例 #2：** ``` 1689 ``` **输入样例 #3：** ``` 69 999900997 ``` **输出样例 #3：** ``` 193862705 ``` **说明：** 在第一个测试案例中，所有排列如下： - $ [1, 2, 3] $，需要 $ 0 $ 次操作； - $ [1, 3, 2] $，需要 $ 1 $ 次操作； - $ [2, 1, 3] $，需要 $ 1 $ 次操作； - $ [2, 3, 1] $，需要 $ 2 $ 次操作； - $ [3, 1, 2] $，需要 $ 2 $ 次操作； - $ [3, 2, 1] $，需要 $ 3 $ 次操作。 因此，答案为 $ 0+1+1+2+2+3=9 $。