← 返回题目列表

Codeforces · 1439/D

D. INOI 决赛

中文机器翻译题面 查看原题

今天是 INOI(伊朗国家信息学奥林匹克竞赛)的决赛。比赛室排成一排,配有 $$$n$$$ 计算机。所有计算机从左到右用从 $$$1$$$ 到 $$$n$$$ 的整数进行编号。有 $$$m$$$ 名参与者,编号为从 $$$1$$$ 到 $$$m$$$ 的整数。

我们有一个长度为 $$$m$$$ 的数组 $$$a$$$,其中 $$$a_{i}$$$ ($$$1 \leq a_i \leq n$$$) 是第 $$$i$$$ 参与者想要坐在后面的计算机。

此外,我们还有另一个长度为 $$$m$$$ 的数组 $$$b$$$,由字符 'L' 和 'R' 组成。 $$$b_i$$$ 是第 $$$i$$$ 参与者进入房间的一侧。 “L”表示参与者从计算机 $$$1$$$ 左侧进入,从左到右,“R”表示参与者从计算机 $$$n$$$ 右侧进入,从右到左。

参与者按照从$$$1$$$到$$$m$$$的顺序一一进入房间。他们中的第 $$$i$$$ 沿着 $$$b_i$$$ 方向进入比赛房间,并坐在第 $$$a_i$$$ 计算机后面。如果它被占用,他会继续朝他的方向走,直到到达第一台未被占用的计算机。之后,他就坐在了它的后面。如果他找不到任何计算机,他就会感到沮丧并放弃比赛。

第 $$$i$$$ 位参与者的疯狂之处在于他分配的计算机 ($$$a_i$$$) 与他最终坐在后面的计算机之间的距离。计算机 $$$i$$$ 和 $$$j$$$ 之间的距离等于 $$$|i - j|$$$。

数组 $$$a$$$ 中的值可以相等。存在 $$$n^m \cdot 2^m$$$ 可能的数组对 $$$(a, b)$$$。

考虑所有数组对$$$(a, b)$$$,这样就不会有人感到不安。对于每个人,我们计算参与者疯狂程度的总和。求所有这些值的总和。

您将得到一些质数模$$$p$$$。通过模 $$$p$$$ 求出该总和。

输入

唯一的一行包含三个整数 $$$n$$$、$$$m$$$、$$$p$$$ ($$$1 \leq m \leq n \leq 500、10^8 \leq p \leq 10 ^ 9 + 9$$$)。

保证数字 $$$p$$$ 是质数。

输出

仅打印一个整数——所需的总和以 $$$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

注意

在第一个测试中,存在三个可能的数组 $$$a$$$:$$$\{1\}$$$、$$$\{2\}$$$ 和 $$$ \{3\}$$$ 以及两个可能的数组 $$$b$$$:$$$\{\mathtt{L}\}$$$ 和 $$$\{\mathtt{R}\}$$$。对于所有六对数组 $$$(a, b)$$$,唯一的参与者将坐在计算机 $$$a_1$$$ 后面,因此他的疯狂程度将为 $$$0$$$。所以疯狂的总和将是$$$0$$$。

在第二个测试中,所有可能的数组对 $$$(a, b)$$$ 使得没有人感到不安是:

- $$$(\{1, 1\}, \{\mathtt{L}, \mathtt{L}\})$$$,疯狂的总和是$$$1$$$;
- $$$(\{1, 1\}, \{\mathtt{R}, \mathtt{L}\})$$$,疯狂的总和为 $$$1$$$;
- $$$(\{2, 2\}, \{\mathtt{R}, \mathtt{R}\})$$$,疯狂的总和是 $$$1$$$;
- $$$(\{2, 2\}, \{\mathtt{L}, \mathtt{R}\})$$$,疯狂的总和是 $$$1$$$;
- \{\{1, 2\}、\{2, 1\}\}$$$ 和 $$$b \in \{\{\mathtt{L}、\mathtt{L}\}、\{\mathtt{R}、\mathtt{L}\}、\{\mathtt{L} 中所有可能的 $$$a 对, \mathtt{R}\},\{\mathtt{R},\mathtt{R}\}\}$$$,疯狂的总和是$$$0$$$。

所以,答案是 $$$1 + 1 + 1 + 1 + 0 \ldots = 4$$$。