309988: CF1768E. Partial Sorting

Memory Limit:1024 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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 $ .

Input

题意翻译

### 题目描述 给定整数 $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$ 取模后的值。

Output

**部分排序**

**题目描述:**
给定整数 $ 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 $。

加入题单

上一题 下一题 算法标签: