INOI Final Contests

题意翻译

考虑数组 $\{ a_m \}, \{ b_m \}$，其中 $1 \leqslant a_i \leqslant n$，$b_i \in \{ \texttt{L}, \texttt{R} \}$。有 $m$ 个人和 $n$ 个位置。$a_i$ 表示第 $i$ 个人希望的位置，$b_i$ 表示第 $i$ 个人从左到右选取位置还是从右到左。 接下来，按照 $1 \sim m$ 的顺序选取位置，每个人根据 $b_i$ 从某个方向开始选取位置。当他到达位置 $a_i$ 时，如果位置 $a_i$ 没有被占用，那么他会选取位置 $a_i$；否则，他会接着选取第一个没有被占用的位置。 定义一对 $(a, b)$ 是合法的，当且仅当不会出现没有位置可选的情况。此时，我们认为 $(a, b)$ 的贡献是每个人实际选取的位置和位置 $a_i$ 的距离之和。 求所有合法的 $(a, b)$ 的贡献和对 $p$ 取模的值。 保证 $m \leqslant n \leqslant 500$，$10^8 \leqslant p \leqslant 10^9 + 9$。

题目描述

Today is the final contest of INOI (Iranian National Olympiad in Informatics). The contest room is a row with $ n $ computers. All computers are numbered with integers from $ 1 $ to $ n $ from left to right. There are $ m $ participants, numbered with integers from $ 1 $ to $ m $ . We have an array $ a $ of length $ m $ where $ a_{i} $ ( $ 1 \leq a_i \leq n $ ) is the computer behind which the $ i $ -th participant wants to sit. Also, we have another array $ b $ of length $ m $ consisting of characters 'L' and 'R'. $ b_i $ is the side from which the $ i $ -th participant enters the room. 'L' means the participant enters from the left of computer $ 1 $ and goes from left to right, and 'R' means the participant enters from the right of computer $ n $ and goes from right to left. The participants in the order from $ 1 $ to $ m $ enter the room one by one. The $ i $ -th of them enters the contest room in the direction $ b_i $ and goes to sit behind the $ a_i $ -th computer. If it is occupied he keeps walking in his direction until he reaches the first unoccupied computer. After that, he sits behind it. If he doesn't find any computer he gets upset and gives up on the contest. The madness of the $ i $ -th participant is the distance between his assigned computer ( $ a_i $ ) and the computer he ends up sitting behind. The distance between computers $ i $ and $ j $ is equal to $ |i - j| $ . The values in the array $ a $ can be equal. There exist $ n^m \cdot 2^m $ possible pairs of arrays $ (a, b) $ . Consider all pairs of arrays $ (a, b) $ such that no person becomes upset. For each of them let's calculate the sum of participants madnesses. Find the sum of all these values. You will be given some prime modulo $ p $ . Find this sum by modulo $ p $ .

输入输出格式

输入格式

The only line contains three integers $ n $ , $ m $ , $ p $ ( $ 1 \leq m \leq n \leq 500, 10^8 \leq p \leq 10 ^ 9 + 9 $ ). It is guaranteed, that the number $ p $ is prime.

输出格式

Print only one integer — the required sum by modulo $ p $ .

输入输出样例

输入样例 #1

3 1 1000000007

输出样例 #1

0

输入样例 #2

2 2 1000000009

输出样例 #2

4

输入样例 #3

3 2 998244353

输出样例 #3

8

输入样例 #4

20 10 1000000009

输出样例 #4

352081045

说明

In the first test, there are three possible arrays $ a $ : $ \{1\} $ , $ \{2\} $ , and $ \{3\} $ and two possible arrays $ b $ : $ \{\mathtt{L}\} $ and $ \{\mathtt{R}\} $ . For all six pairs of arrays $ (a, b) $ , the only participant will sit behind the computer $ a_1 $ , so his madness will be $ 0 $ . So the total sum of madnesses will be $ 0 $ . In the second test, all possible pairs of arrays $ (a, b) $ , such that no person becomes upset are: - $ (\{1, 1\}, \{\mathtt{L}, \mathtt{L}\}) $ , the sum of madnesses is $ 1 $ ; - $ (\{1, 1\}, \{\mathtt{R}, \mathtt{L}\}) $ , the sum of madnesses is $ 1 $ ; - $ (\{2, 2\}, \{\mathtt{R}, \mathtt{R}\}) $ , the sum of madnesses is $ 1 $ ; - $ (\{2, 2\}, \{\mathtt{L}, \mathtt{R}\}) $ , the sum of madnesses is $ 1 $ ; - all possible pairs of $ a \in \{\{1, 2\}, \{2, 1\}\} $ and $ b \in \{\{\mathtt{L}, \mathtt{L}\}, \{\mathtt{R}, \mathtt{L}\}, \{\mathtt{L}, \mathtt{R}\}, \{\mathtt{R}, \mathtt{R}\}\} $ , the sum of madnesses is $ 0 $ . So, the answer is $ 1 + 1 + 1 + 1 + 0 \ldots = 4 $ .

题意翻译

考虑数组 $\{ a_m \}, \{ b_m \}$，其中 $1 \leqslant a_i \leqslant n$，$b_i \in \{ \texttt{L}, \texttt{R} \}$。有 $m$ 个人和 $n$ 个位置。$a_i$ 表示第 $i$ 个人希望的位置，$b_i$ 表示第 $i$ 个人从左到右选取位置还是从右到左。 接下来，按照 $1 \sim m$ 的顺序选取位置，每个人根据 $b_i$ 从某个方向开始选取位置。当他到达位置 $a_i$ 时，如果位置 $a_i$ 没有被占用，那么他会选取位置 $a_i$；否则，他会接着选取第一个没有被占用的位置。 定义一对 $(a, b)$ 是合法的，当且仅当不会出现没有位置可选的情况。此时，我们认为 $(a, b)$ 的贡献是每个人实际选取的位置和位置 $a_i$ 的距离之和。 求所有合法的 $(a, b)$ 的贡献和对 $p$ 取模的值。 保证 $m \leqslant n \leqslant 500$，$10^8 \leqslant p \leqslant 10^9 + 9$。