问题 C: 教练的疑惑
内存限制:512 MB
时间限制:1.000 S
评测方式:文本比较
命题人:
提交:10
解决:2
题目描述
教练要带队去打比赛,比赛队伍一共有m个人,教练希望从自己的队员中选择m个队员,使所选出来的队员不能出现矛盾(队内任意两个人的能力值不能相同且任意两个人的能力值差要小于m)
教练陷入了疑惑当中,请聪明的你教练算算教练一共有多少种组队的方法。答案可能过大,请对109+7取模后输出
教练陷入了疑惑当中,请聪明的你教练算算教练一共有多少种组队的方法。答案可能过大,请对109+7取模后输出
输入
第一行输入一个数T 代表有T组测试案例)
对于每个案例:
第一行输入两个数n,m
第二行和第三行每行输入n个数 代表有ai个队员的能力值为bi (bi>bi-1)
数据范围:1≤m≤n 1≤ai≤109 bi的和不超过108 n的和不超过107
输入数据较多建议使用快读。
对于每个案例:
第一行输入两个数n,m
第二行和第三行每行输入n个数 代表有ai个队员的能力值为bi (bi>bi-1)
数据范围:1≤m≤n 1≤ai≤109 bi的和不超过108 n的和不超过107
输入数据较多建议使用快读。
输出
对于每个案例输出一个答案代表对应的方法数
样例输入 复制
8
6 4
6 7 8 9 10 11
1 1 1 1 2 1
4 3
2 3 4 6
2 1 1 1
4 2
1 2 3 5
2 2 3 1
1 3
3
3
4 1
3 4 7 10
2 1 1 1
1 1
1
1
3 2
1 2 3
1 1 1
2 2
1 2
1 1
样例输出 复制
5
2
10
0
5
1
2
1
提示
对于案例解释:
6 4
6 7 8 9 10 11
1 1 1 1 2 1
共有[6,7,8,9,10,10,11] 7个队员。
教练选择能力值为6 7 8 9的队员有1种选法; 教练选择能力值为7 8 9 10的队员有2种选法;
教练选择能力值为8 9 10 11的队员有2种选法;
总共五种选法故输出答案为5.
6 4
6 7 8 9 10 11
1 1 1 1 2 1
共有[6,7,8,9,10,10,11] 7个队员。
教练选择能力值为6 7 8 9的队员有1种选法; 教练选择能力值为7 8 9 10的队员有2种选法;
教练选择能力值为8 9 10 11的队员有2种选法;
总共五种选法故输出答案为5.