G. Doping
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\).
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\).
Print \(n\) integers, where the \(k\)-th integer is the number of \(k\)-special permutations modulo \(m\).
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]\).