AdditionalFile4104.zip

P9419 [POI 2021/2022 R1] Układanie kart

题目背景

译自 XXIX Olimpiada Informatyczna – I etap Układanie kart。

题目描述

我们用以下方法将一个排列递增排序:

一次操作：记第一个数字为 $k$，在排列中找到 $k-1$（$k=1$ 则取 $n$），把 $k-1$ 拉到排列的第一个位置，中间的数字依次后移。

一次操作的价值：$k-1$（或 $n$）在原排列的位置（这个从 $0$ 开始标号）。

一个排列的价值：进行若干次操作直到排列有序，价值为每次操作的价值之和。

给你 $n,m$，求所有 $n!$ 个排列的价值之和，对 $m$ 取模。

输入格式

一行两个正整数，$n,m$。

输出格式

一行一个整数，答案对 $m$ 取模的结果。

输入输出样例 #1

输入 #1

2 100

输出 #1

1

输入输出样例 #2

输入 #2

3 100

输出 #2

15

输入输出样例 #3

输入 #3

10 1000

输出 #3

100

输入输出样例 #4

输入 #4

500 100000

输出 #4

60000

输入输出样例 #5

输入 #5

100000 1000

输出 #5

0

说明/提示

对于所有数据，$2\leq n\leq 1000000$，$2\leq m\leq 10^9$。

子任务编号	附加限制	分数
1	$n\leq 10$	10
2	$n\leq 2000$	60
3		30

#4104. 「POI 2021/2022 R1」Układanie kart

标签: 传统 | 时间限制: 4000 ms | 内存限制: 256 MiB |

题目描述

题目译自 XXIX Olimpiada Informatyczna – I etap Układanie kart

Bajtazar 喜欢玩桥牌，但是他不知道如何快速地整理在手上的牌。所以他决定在和朋友们玩下一局之前，先练习一下整理牌。

为此，他准备了一副特殊的训练牌，共有 $n$ 张牌，从 $1$ 到 $n$ 编号。他的练习从洗牌开始，他会给他手上的牌一个随机的排列。然后他想按照升序的顺序来排列这些牌。

在牌没有排序之前，Bajtazar 执行以下操作：他看着手上的第一张牌的编号（记为 $k$ ），然后在手上找到编号为 $k-1$ 的牌（除非 $k=1$，那么他就找到编号为 $n$ 的牌），然后把它放到牌的最前面。这个操作的时间为找到的牌距离牌的开头的距离。排序牌的时间是所有执行操作的时间的总和。

例如，将排列 $5\,6\,3\,7\,1\,4\,2$ 进行排序的时间是 $5+3+6+6=20$ ，因为连续的操作序列是：

$$5\,6\,3\,7\,1\,\underline{4}\,2\,\xrightarrow{5} 4\,5\,6\,\underline{3}\,7\,1\,2 \xrightarrow{3} 3\,4\,5\,6\,7\,1\, \underline{2} \xrightarrow{6} 2\,3\,4\,5\,6\,7\,\underline{1} \xrightarrow{6} 1\,2\,3\,4\,5\,6\,7$$

Bajtazar 想要练习所有 $n!$ 种可能的排列的排序。写一个程序计算出完成这个壮举所需要的总时间，让他放弃这个想法。你只需要计算出时间对给定的数 $m$ 取模的结果。

输入格式

输入一行，包含两个整数 $n, m\ (2 \leq n \leq 10^6, 2 \leq m \leq 10^9)$。

输出格式

输出的一行一个整数，表示用 Bajtazar 的方法对所有排列进行排序的总时间模 $m$ 的结果。

样例 1

输入

2 100

输出

1

我们有两种排列：$1\,2$（时间 $0$）和 $2\,1$（时间 $1$）。

样例 2

见附加文件下 [ukl1.in](file:ukl1.in) 和 [ukl1.out](file:ukl1.out)。

该样例满足 $n=3, m=100$，答案是 $15$。

样例 3

见附加文件下 [ukl2.in](file:ukl2.in) 和 [ukl2.out](file:ukl2.out)。

该样例满足 $n=10, m=1000$，答案是 $100$。

样例 4

见附加文件下 [ukl3.in](file:ukl3.in) 和 [ukl3.out](file:ukl3.out)。

该样例满足 $n=500, m=10^5$，答案是 $60000$。

样例 5

见附加文件下 [ukl4.in](file:ukl4.in) 和 [ukl4.out](file:ukl4.out)。

该样例满足 $n=10^5, m=1000$，答案是 $0$。

数据范围与提示

详细子任务附加限制及分值如下表所示。

子任务编号	附加限制	分值
$1$	$n \leq 10$	$10$
$2$	$n \leq 2000$	$60$
$3$	无附加限制	$30$