menu ZJOJ
account_circle 请登录
home
首页
book
题目
apps
分类
play_circle_outline
状态
assessment
竞赛
assignment
作业
equalizer
排名
assignment_ind
登录
person_add
注册
1184: 韩信点兵
时间限制:1.000s
内存限制:128MB

题目描述

    话说,韩信将军神机妙算,兵法娴熟,武艺超群,同时还是一位独具慧眼的将军,能够一眼看出士兵的武艺值 X。一次执行任务,韩信将军到校场点兵,已知校场一共有N位士兵,士兵们的武艺值高低不齐。

    随军主簿说一共要选M位士兵,并且要满足所挑选士兵的武艺值 X 依次严格递增。(从第一名士兵开始选,可以选也可以不选,只要满足武艺值递增且人数满足M就算一种方案。)

    韩信将军眯了眯眼睛,立即说出了所有可能选择方案数。

    数据范围: 1 <= M <= N <= 1000 ,每一个士兵的武艺值 X ( 1 <= X <= 10^9)

输入格式

    第一行输入一个正整数num,代表一共有num组测试数据。( 1 <= num <= 100)

    对于每组数据,第一行包含两个整数N和M,N代表士兵总数,M代表挑选的士兵数。

    第二行包含N个整数,表示士兵的武艺值X。

输出格式

    每组数据输出一个结果,每个结果占一行。

    输出格式为“Answer #a: b”,a为数据组别序号,从1开始,b为结果。

    由于数据可能很大,请你输入对 10^9+10 取模后的结果。

样例输入 content_copy

3
5 2
4 5 1 6 7
4 2
1 2 3 4
3 1
1 2 3

样例输出 content_copy

Answer #1: 8
Answer #2: 6
Answer #3: 3

提示/说明

别想多了哦,知识简单的dp。

测试数据包含多组。

分类