6003: 进阶7.9.2 有序子序列
内存限制：1024 MB
时间限制：3.000 S
评测方式：文本比较
命题人：
提交：16
解决：5
题目描述
给定数字序列(A1,A2,…,An)的子序列是任意序列(Ai1,Ai2,…,Aik)，其中1≤i1<i2<ik<n；若子序列是严格逻辑递增的，则称之为有序子序列， 如：序列 (1,7,3,5,9,4,8)的子序列为(1,7)、(3,4,8)等。
给定数字序列，求解其长度为m的有序子序列的个数。
给定数字序列，求解其长度为m的有序子序列的个数。
输入
输入包含多个测试样例，总数量不超过100，每个样例包含两行；
- 第1行，包含两个整数n(1≤n≤10000)和m(1≤m≤100)，n表示序列长度，m表示需要查找的有序子序列的长度；
- 第2行，包含序列的n个整数元素，每个元素的范围都为0~987654321。
输出
对于每个测试样例，都输出“答案%(取模)123456789”的结果。
样例输入 复制
3 2
1 1 2
7 3
1 7 3 5 9 4 8样例输出 复制
2
12