#P2489. Random Sequence

    ID: 1544 传统题 1000ms 128MiB 尝试: 168 已通过: 49 难度: 7 上传者: 标签>CF2200提高一维前缀和对称性分析期望线性性指示变量随机游走反射原理组合数乘法递推acm

Random Sequence

题目描述

There is a random sequence LL whose element are all random numbers either −1-1 or 11 with the same possibility.Now we define MAVS,the abbreviate of Maximum Absolute Value Subsequence,to be any (if more than one) subsequences of LL whose absolute value is maximum among all subsequences.Given the length of LL,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 TT.TT positive integers follow,each of which contains one positive number not greater than 15001500 denoted the length of LL.

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

输出格式

For each test case,output the expectation you are required to calculate.Answers are rounded to 66 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=62+1+1+2=6。
6/4=1.56/4=1.5

题目来源

acm 2011 福州