K-inversions#4952

K-inversions

1 sekunt

64 megabaýt

Örän ýeňil

Consider a permutation $a_{1}, a_{2}, \dots, a_{n}$ a_1, a_2, \ldots, a_n (all $a_{i}$ a_i are distinct integers from $1$ to $n$ ). We define a $k$ -inversion as a sequence of numbers $i_{1}, i_{2}, \dots, i_{k}$ i_1, i_2, \ldots, i_k such that

1 \leq i_{1} < i_{2} < \dots < i_{k} \leq n

1 \leq i_1 < i_2 < \cdots < i_k \leq n

and

a_{i_{1}} > a_{i_{2}} > \dots > a_{i_{k}} .

a_{i_1} > a_{i_2} > \cdots > a_{i_k}.

Your task is to determine the number of different $k$ -inversions in the given permutation.

Giriş

The first line contains two integers $n$ and $k$ ( $1 \leq n \leq 20000$ 1 \leq n \leq 20000, $2 \leq k \leq 10$ 2 \leq k \leq 10). The second line contains $n$ integers $a_{1}, a_{2}, \dots, a_{n}$ a_1, a_2, \ldots, a_n — the permutation.

Çykyş

Output a single integer: the number of $k$ -inversions in the given permutation, modulo $1 0^{9}$ 10^9.

Mysallar

1-nji mysal

Loading

a_{1}, a_{2}, \dots, a_{n}

a_{i}

i_{1}, i_{2}, \dots, i_{k}

1 \leq i_{1} < i_{2} < \dots < i_{k} \leq n

a_{i_{1}} > a_{i_{2}} > \dots > a_{i_{k}} .

1 \leq n \leq 20000

2 \leq k \leq 10

a_{1}, a_{2}, \dots, a_{n}

1 0^{9}