GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

Sunday 6 November 2022

[Solution] Doping Codeforces Solution



G. Doping
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

We call an array a of length n fancy if for each 1<in it holds that ai=ai1+1.

Let's call f(p) applied to a permutation 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 than p, and
  • f(p)=k.

Your task is to count for each 1kn the number of k-special permutations modulo m.

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

 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

The first line contains two integers n and m (1n200010m109) — the length of the permutation and the required modulo.

The second line contains n distinct integers p1,p2,,pn (1pin) — the permutation p.

Output

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

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

No comments:

Post a Comment