7447: Blood Pressure Game
内存限制：128 MB
时间限制：1 S
题面：传统
评测方式：文本比较
上传者：
提交：0
通过：0
题目描述
Gugulu, a JBer, who was an ACMer two years ago, comes to HDOJ taking part in the 2020 Multi
University Training Contest again. However, every time when Gugulu came to regional, he always got
an Iron Medal and would consider this competition JB-like. To release his pain, Gugulu would go to
the Shanghai Disneyland Park to have fun in taking the Roller Coaster. Gugulu loves the feeling with
high-level blood pressure so much which makes him feel like a happy flflappy bird who forgets all the Wrong
Answers and Time Limit Exceededs etc.
We can regard the path of the Roller Coaster as a list of turning points with difffferent heights which can
be represented as an array {a1, a2, a3, . . . , an} of size n, and Gugulu’s fifinal blood pressure after the game
of the Roller Coaster is counted as the sum of all absolute values of the difffferences between the n n 1
pairs of adjacent array numbers, i.e. Pnn
1
i=1
|ai i ai+1|.
Gugulu always got Iron Medals and is always getting Iron Medals, which makes him keep taking the
Roller Coaster over and over again. However, as playing more games, his threshold on the value of blood
pressure which can make himself happy is keeping increasing. As a result, the Roller Coaster of Shanghai
Disneyland Park can hardly meet Gugulu’s needs anymore.
Therefore, Gugulu decides to rearrange the array {a1, a2, a3, . . . , an} in any order to make his blood
pressure as high as possible. Moreover, he wants to know the largest k distinct possible values of blood
pressure that can be achieved and the number of the corresponding permutations.
You, another JBer, are sure that Gugulu is clever enough to get the highest blood pressure as he can. It is
very important for you to calculate the correct answer to make an appointment with a proper cardiologist
in advance to save Gugulu’s life. You must solve this problem! Gugulu’s blood pressure is becoming out
of control!
输入格式
The fifirst line of the input contains the number of test cases, T (1 ≤ T ≤ 5). T test cases follow.
For each test case, the fifirst line contains two integers, n (2 ≤ n ≤ 600) and k (1 ≤ k ≤ 20).
Then, in second line, there are n integers {a1, a2, a3, . . . , an} (1 ≤ ai ≤ 106
), denoting the n original Roller
Coaster turning points. As it is an exciting Roller Coaster, it is guaranteed that all n integers in the array
are pairwise difffferent.
输出格式
For each test case, output k lines. For the i-th (1 ≤ i ≤ k) line, print two numbers wi and ci
, where wi
denotes the i-th largest possible value of blood pressure that can be achieved and ci denotes the number
of corresponding permutations modulo 109 + 7. Note that when the i-th largest possible value doesn’t
exist, print “-1” instead.
输入样例 复制
1
4 8
1 3 7 9输出样例 复制
20 2
18 4
16 2
14 8
12 2
10 4
8 2
-1