https://vn.spoj.com/problems/KINV
https://oj.vnoi.info/problem/KINV
Cho dãy N số nguyên dương A[1] , … A[N] là một hoán vị của 1 , 2 , 3 , … N .
Một dãy nghịch thế độ dài k là 1 dãy A[j1] > A[j2] > A[j3] … > A[jk] với j1 < j2 < j3 … < jk . Hãy đếm xem có tất cả bao nhiêu dãy nghịch thế độ dài k .
Dòng 1 : 2 số nguyên dương N và k ( 2 ≤ N ≤ 10000 , 2 ≤ k ≤ 10 ) .
Dòng 2 : N số nguyên dương A[1] … A[N] .
Giả sử T là số lượng dãy nghịch thế có độ dài k , hãy ghi ra T mod 10^9 .
Input
3 2
3 2 1
Output
3
Gọi F[i,j] là số lượng dãy nghịch thế độ dài i và kết thúc ở vị trí j. Vậy F[i,j] sẽ được tính từ các F[i-1,j1] với j1 từ 1 đến j-1 thỏa mãn a[j1] > a[j]. Khi tính F[i,j] thì làm tương tự NKINV, nhưng lúc cập nhật thì không phải là cộng thêm 1 mà cộng thêm F[i,j].
Kết quả là tổng của các F[k,i] với i từ 1 đến n.