303066: CF597C. Subsequences

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Subsequences

题意翻译

- 给定一个 $1\sim n$ 的排列 $a$,求 $a$ 中长度为 $k+1$ 的上升子序列个数。 - $1\le n\le 10^5$,$0\le k\le 10$,答案不超过 $8\times 10^{18}$。

题目描述

For the given sequence with $ n $ different elements find the number of increasing subsequences with $ k+1 $ elements. It is guaranteed that the answer is not greater than $ 8·10^{18} $ .

输入输出格式

输入格式


First line contain two integer values $ n $ and $ k $ $ (1<=n<=10^{5},0<=k<=10) $ — the length of sequence and the number of elements in increasing subsequences. Next $ n $ lines contains one integer $ a_{i} $ ( $ 1<=a_{i}<=n $ ) each — elements of sequence. All values $ a_{i} $ are different.

输出格式


Print one integer — the answer to the problem.

输入输出样例

输入样例 #1

5 2
1
2
3
5
4

输出样例 #1

7

Input

题意翻译

- 给定一个 $1\sim n$ 的排列 $a$,求 $a$ 中长度为 $k+1$ 的上升子序列个数。 - $1\le n\le 10^5$,$0\le k\le 10$,答案不超过 $8\times 10^{18}$。

加入题单

上一题 下一题 算法标签: