Doping
Contest: CodeTON Round 3 (Div. 1 + Div. 2, Rated, Prizes!)
Difficulty rating: 3300
Tags: combinatorics, dp, math

We call an array $$$a$$$ of length $$$n$$$ fancy if for each $$$1 < i \le n$$$ it holds that $$$a_i = a_{i-1} + 1$$$.

Let's call $$$f(p)$$$ applied to a permutation$$$^\dagger$$$ of length $$$n$$$ as the minimum number of subarrays it can be partitioned such that each one of them is fancy. For example $$$f([1,2,3]) = 1$$$, while $$$f([3,1,2]) = 2$$$ and $$$f([3,2,1]) = 3$$$.

Given $$$n$$$ and a permutation $$$p$$$ of length $$$n$$$, we define a permutation $$$p'$$$ of length $$$n$$$ to be $$$k$$$-special if and only if:

- $$$p'$$$ is lexicographically smaller$$$^\ddagger$$$ than $$$p$$$, and
- $$$f(p') = k$$$.

Your task is to count for each $$$1 \le k \le n$$$ the number of $$$k$$$-special permutations modulo $$$m$$$.

$$$^\dagger$$$ A permutation 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).

$$$^\ddagger$$$ A permutation $$$a$$$ of length $$$n$$$ is lexicographically smaller than a permutation $$$b$$$ of length $$$n$$$ if and only if the following holds: in the first position where $$$a$$$ and $$$b$$$ differ, the permutation $$$a$$$ has a smaller element than the corresponding element in $$$b$$$.

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 2000$$$, $$$10 \le m \le 10^9$$$) — the length of the permutation and the required modulo.

The second line contains $$$n$$$ distinct integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$) — the permutation $$$p$$$.

Output format:
Print $$$n$$$ integers, where the $$$k$$$-th integer is the number of $$$k$$$-special permutations modulo $$$m$$$.

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

Note:
In the first example, the permutations that are lexicographically smaller than $$$[1,3,4,2]$$$ are:

- $$$[1,2,3,4]$$$, $$$f([1,2,3,4])=1$$$;
- $$$[1,2,4,3]$$$, $$$f([1,2,4,3])=3$$$;
- $$$[1,3,2,4]$$$, $$$f([1,3,2,4])=4$$$.

Thus our answer is $$$[1,0,1,1]$$$.

In the second example, the permutations that are lexicographically smaller than $$$[3,2,1]$$$ are:

- $$$[1,2,3]$$$, $$$f([1,2,3])=1$$$;
- $$$[1,3,2]$$$, $$$f([1,3,2])=3$$$;
- $$$[2,1,3]$$$, $$$f([2,1,3])=3$$$;
- $$$[2,3,1]$$$, $$$f([2,3,1])=2$$$;
- $$$[3,1,2]$$$, $$$f([3,1,2])=2$$$.

Thus our answer is $$$[1,2,2]$$$.

Example input:
4 666012
1 3 4 2

Example output:
1 0 1 1

Example input:
3 10
3 2 1

Example output:
1 2 2

Editorial:
Consider a permutation $$$p$$$ that lexicographically smaller than given permutation, assume the first different position is $$$k$$$, if we fix $$$p_k$$$, the remaining numbers $$$a_{k+1},a_{k+2},...,a_n$$$ can be arranged in any order. Denote $$$S$$$ as the set of remaining numbers. Let $$$m$$$ be the number of consecutive pairs, $$$m=|\{x|x \in S,(x-1) \in S\cup\{p_k\} \}|$$$, $$$p_k$$$ is included because it is possible that $$$p_{k+1}=p_k+1$$$. Fix the number of positions that $$$p_i=p_{i-1}+1$$$, this consumes some consecutive pairs, the remaining consecutive pairs should not increase the number of positions. Define a sequence $$$p$$$ good if and only if it has no $$$i$$$ that $$$p_i=p_{i-1}+1$$$.
Consider $$$dp[i][j]$$$ = number of good arrangements of $$$i$$$ values with $$$j$$$ consecutive pairs. Consider one consecutive pair, if it is the only wrong pair, the number of values decrease by one and this situation should be excluded, otherwise this pair can be ignored, so $$$dp[i][j]=dp[i][j-1]-dp[i-1][j-1]$$$, with boundary $$$dp[i][0]=i!$$$. After enumrating $$$k$$$, let $$$S'=\{a_k,a_{k+1},...,a_n\}$$$, $$$p_k$$$ is chosen from $$$S'$$$ and $$$p_k<a_k$$$. Assume $$$p_k=x$$$, if $$$x-1 \in S'$$$, the number of consecutive pairs decrease by one, otherwise it stay the same. Additionally, if $$$x \ne p_{k-1}+1$$$, the number of subarrays increase by one. For every situation, count the number of $$$p_k$$$ and then calculate answer.
Time complexity: $$$O(n^2)$$$.