Number of Permutations
Time limit2sMemory limit128 MB
Given a permutation's up-down pattern, count permutations of size n sharing the same pattern, modulo 1,000,000,000.
- Level
Medium5 of 10
- Topics
- Dynamic programming, Combinatorics
- Solved
- No attempts yet
Problem
Let A = (a_1, a_2, ..., a_n) be a permutation of the set X = {1, 2, 3, ..., n}. That is, different positions contain different values, and every value belongs to X.
For a permutation A, define a sequence P(A) = (p_1, p_2, ..., p_{n-1}) of length n - 1 as follows. For each i(1 <= i <= n - 1), if a_i > a_{i+1}, then p_i = 0; otherwise, p_i = 1.
Given n and a permutation A, count the permutations B of X such that P(B) = P(A). The permutation A itself is included in the count.
When A = (1, 3, 2, 4), P(A) = (1, 0, 1). The permutations with this same pattern are (1, 3, 2, 4), (1, 4, 2, 3), (2, 3, 1, 4), (2, 4, 1, 3), and (3, 4, 1, 2), so the count is 5.
Input
The first line contains the size n of the set X. The value n is a positive integer not greater than 5,000.
The second line contains the permutation A of X, written as n space-separated integers.
Output
Print the number of permutations B such that P(B) = P(A). Since the answer can be very large, print it modulo 1,000,000,000.