问题 DG: 子序列的极差和
内存限制:128 MB
时间限制:3.000 S
评测方式:文本比较
命题人:
提交:79
解决:17
题目描述
我们知道,对于一个序列,它的极差是序列中的最大值减去最小值。
同时我们知道,一个序列的子序列是由它本身删去若干个元素得到的。
现在给一个长度为 $n$ 的序列,你需要求出其所有长度为 $k$ 的子序列的极差之和。
(由于这个答案很大,所以你输出的结果需要对 $10^9+7$ 取模)
同时我们知道,一个序列的子序列是由它本身删去若干个元素得到的。
现在给一个长度为 $n$ 的序列,你需要求出其所有长度为 $k$ 的子序列的极差之和。
(由于这个答案很大,所以你输出的结果需要对 $10^9+7$ 取模)
输入
第一行,输入两个整数,$n,k$ ($1 \leq k \leq n \leq 10^5$)
第二行,输入 $n$ 个整数 $a_i$ ,代表这个序列 ($|a_i| \leq 10^9$)
第二行,输入 $n$ 个整数 $a_i$ ,代表这个序列 ($|a_i| \leq 10^9$)
输出
输出其所有长度为 $k$ 的子序列的极差之和对$10^9+7$ 取模的结果
样例输入 复制
4 2
1 1 3 4
样例输出 复制
11
提示
长度为2的子序列共有6个,分别是$ \{1,1\},\{1,3\},\{1,4\},\{1,3\},\{1,4\}, \{3,4\}$,它们的极差和是11