Randomly Reverse

Time Limit: 10000/5000MS (Java/Others) Memory Limit: 256000/128000KB (Java/Others)

Problem Description

Given a array A with N elements, and you can perform the following operation several times: randomly choose two indexes l and r (l < r) and reverse A[l...r] (both inclusive). 
After you perform the operation above K times, you randomly choose two indexes l and r (l < r) and calculate the S = sum(A[l...r]) (both inclusive). Now you are to calculate the expected value of S.
If you are not familiar with the "reverse" operation, you can see the following example: If you have a array A = [1, 2, 3, 4], the reversed array of A would be A' =  [4, 3, 2, 1].

Input

The first line of input file contains an integer T indicating the number of case.
In each test case:
The first line contains two integers N and K. (1 <= N <= 1000, 0 <= K <= 10)
The next line contains N integers which are the elements of array A. (0 <= A[i] <= 1,000,000,000)

Output

For each test case:
Output the expected value of S which should accurate to four decimal places.

Sample Input

2
3 1
1 2 3
3 2
1 2 3

Sample Output

4.6667
4.6667

Source

dut200901102

Manager

Information
Solved Number4
Submit Number38
Problem Tags
dp
probabilities
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel