题目描述

There is a random sequence $L$ whose element are all random numbers either $-1$ or $1$ with the same possibility．Now we define MAVS，the abbreviate of Maximum Absolute Value Subsequence，to be any （if more than one） subsequences of $L$ whose absolute value is maximum among all subsequences．Given the length of $L$，your task is to find the expectation of the absolute value of MAVS．

输入格式

There is only one input file．The first line is the number of test cases $T$．$T$ positive integers follow，each of which contains one positive number not greater than $1500$ denoted the length of $L$．

给你一个数字 $L$，代表数字串长。这个数字串每个元素为 $1$ 或 $-1$。
那么就有这个数列有 $2^L$ 种可能。
现对每个可能的数字串，求其连续子串和，并将和取绝对值，记下最大的那个值。
再求出所有这些值的总和。
输入总和/ $2^L$。

输出格式

For each test case，output the expectation you are required to calculate．Answers are rounded to $6$ numbers after the decimal point．（as shown in the sample output）

3
1
5
10

Case 1: 1.000000
Case 2: 2.750000
Case 3: 4.167969

提示

当输入2时，有

1 1
1 -1
-1 1
-1 -1

这四种可能，其对应的值分别为 $2+1+1+2=6$。
$6/4=1.5$

题目来源

acm 2011 福州