INOI Final Contests
Contest: Codeforces Round 684 (Div. 1)
Difficulty rating: 3100
Tags: combinatorics, dp, fft

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

Input format:
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.

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

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

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

Example input:
3 1 1000000007

Example output:
0

Example input:
2 2 1000000009

Example output:
4

Editorial:
Suppose $$$n = m$$$. Let $$$dp1_i$$$ be the number of $$$(A , B)$$$ pairs for $$$i$$$ participants and $$$i$$$ computers so that no one gets upset. For updating this array we can consider the last participant, and where he will sit. Suppose he sits behind the $$$j$$$-th computer. If he comes from left to right, there are $$$i$$$ choices of computers for him to sit behind, and if he comes from right to left there are $$$n - i + 1$$$ choices for him. If the last participant sits behind the $$$j$$$-th computer there are $$$dp1_{j-1} \cdot dp1_{i-j}$$$ $$${i-1}\choose{j-1}$$$ ways to fill in the rest of the seats because after removing we have two independent subsegments. So $$$dp1_i = (i+1) \sum_{j=1}^{i} dp1_{j-1} \cdot dp1_{i-j}$$$ $$${i-1}\choose{j-1}$$$.
Now let $$$dp2_i$$$ be the sum of the total madnesses for all cases with $$$i$$$ participants and $$$i$$$ computers. Imagine the last person sitting on the $$$j$$$-th computer. The madness of every participant except the last one is $$$(i+1) \cdot (dp2_{j-1} \cdot dp1_{i-j} + dp2_{i-j} \cdot dp1_{j-1})$$$ $$${i-1}\choose{j-1}$$$. However, the madness of the last participant is $$$($$$ $$${j-1}\choose{2}$$$ $$$+$$$ $$${i-j}\choose{2}$$$ $$$) \cdot dp1_{j-1}\cdot dp1_{i-j}$$$ $$${i-1}\choose{j-1}$$$.
Now what if $$$n > m$$$? Suppose $$$dp3_{i ,j}$$$ is the number of $$$(A , B)$$$ pairs for $$$i$$$ computers and $$$j$$$ participants so that no one gets upset. For updating it we can consider the maximal suffix that all of the computers in that suffix will get occupied by participants. Consider its lenghth is $$$l$$$ . If $$$l = 0$$$ then we add $$$dp3_{i-1,j}$$$ to $$$dp3_{i,j}$$$; if not, we add $$$dp1_l \cdot dp3_{i-l-1,j-l}$$$ $$${j}\choose{l}$$$ to $$$dp3_{i, j}$$$. The update is similar to $$$dp1$$$. The update is done correctly because the subsegments are independant.
At last, suppose $$$dp4_{i, j}$$$ is the sum of the total madnesses for all cases with $$$i$$$ computers and $$$j$$$ participants. Consider $$$l$$$ to be the lenghth of the maximal suffix that all of the computers in that suffix will get occupied by participants. If $$$l = 0$$$ then to $$$dp4_{i, j}$$$ we add $$$dp4_{i - 1, j}$$$. If $$$l > 0$$$ then $$$(dp4_{i-1-l, j-l} \cdot dp1_l + dp3_{i-1-l,j-l} \cdot dp2_l)$$$ $$${j}\choose{l}$$$ is added to $$$dp4_{i, j}$$$. The answer shall be $$$dp4_{n, m}$$$.
Time complexity: $$$O(n^3)$$$. Computing $$$dp1$$$ and $$$dp2$$$ is an $$$O(n^2)$$$ task, while computing $$$dp3$$$ and $$$dp4$$$ has a complexity of $$$O(n^3)$$$.
Challenge: Can you find a solution with a better time complexity?