Problem Statement   John has a sequence of digits.
He and Brus will now play with the sequence.
First, John will repeat the following operation k times:
He will choose two different positions in the sequence, and swap the elements at those positions.
(John makes each choice uniformly at random.
That is, each time John chooses two positions, each pair of different positions has the same probability of being chosen.)
Afterwards, Brus will randomly choose a nonempty contiguous subsequence of John's sequence.
He will compute the sum of all elements in the chosen subsequence and he will write it down on a piece of paper.
(Brus also makes his choice uniformly at random.
That is, each possible contiguous subsequence has the same probability of being chosen.)
You are given a String[] sequence.
Concatenate all elements of sequence to get the string s.
For each i, the ith character of s is a digit ('0''9') representing the digit at index i in John's original sequence.
Return the expected value of the sum Brus writes down.   Definition   Class:  TheSwapsDivOne  Method:  find  Parameters:  String[], int  Returns:  double  Method signature:  double find(String[] sequence, int k)  (be sure your method is public) 
    Notes    The returned value must be accurate to within a relative or absolute value of 1E9.   Constraints    sequence will contain between 2 and 47 elements, inclusive.    Each element of sequence will contain between 1 and 47 characters, inclusive.    Each element of sequence will consist of only decimal digits ('0''9').    k will be between 1 and 1,000,000, inclusive.   Examples  0)     Returns: 10.0  There are three equally likely swaps John might make.
If the first two elements are swapped, John will get the sequence {7,4,7}.
Then Brus chooses one of the six possible subsequences.
Their sums are 7, 4, 7, 11, 11 and 18.
Thus the expected value is (7 + 4 + 7 + 11 + 11 + 18)/6 = 29/3.
If the first and the last elements are swapped, the sequence becomes {7,7,4}, and the subsequence sums are 7, 7, 4, 14, 11 and 18.
The expected value in this case is (7 + 7 + 4 + 14 + 11 + 18)/6 = 61/6.
When the last two elements are swapped, the sequence doesn't change and the expected value is equal to 61/6 as well.
Finally, the overall expected value is equal to (29/3 + 61/6 + 61/6)/3 = 10.


 1)     2)    {"1", "1", "1", "1", "1", "1", "1"}  1000000 
 Returns: 3.0  
 3)    {"572685085149095989026478064633266980348504469", "19720257361", "9", "69"}  7 
 Returns: 98.3238536775161  

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.
