随着武陵工业 325 期的开展,武陵地区的生态发生了巨大的变化。现如今,清波寨到武陵城的水路上按顺序分布着 $$$n$$$ 座关口,编号依次为 $$$1, 2, \dots, n$$$。乘坐竹筏从 $$$i-1$$$ 号关口航行至 $$$i$$$ 号关口需要花费 $$$t_i$$$ 单位的时间($$$2 \le i \le n$$$)。
每座关口均设有周期性的通行限制:关口会在"开启"和"关闭"两种状态之间交替切换,每次维持某一状态的时间均为 $$$k$$$ 个单位时间(即一个完整的开闭周期长度为 $$$2k$$$)。当关口处于开启状态时,竹筏可以瞬间渡过(不花费时间);当关口处于关闭状态时,竹筏必须在关口前等待,直到关口切换为开启状态方可通行。
作为终末地的干员,小 H 在伊冯的帮助下侵入了中枢系统。他拥有最高权限,可以在出发前,任意设定每一座关口的初始启动时间。然而,由于水路环境的复杂性与系统底层的不可控延迟,小 H 抵达起点的时机无法与系统精准同步。通俗地说:当小 H 在时刻 $$$0$$$ 恰好到达 $$$1$$$ 号关口前准备出发时,$$$1$$$ 号关口刚好处于周期的哪个时刻是完全随机的。
形式化地说:
现在,小 H 需要乘坐竹筏依次渡过这 $$$n$$$ 座关口前往武陵城。已知他会采取最完美的策略来设定所有的 $$$S_i$$$ 以最小化行程耗时。 请问从时刻 $$$0$$$ 出发开始计时,小 H 只会也只可能采取最优策略的情况下,直到小 H 成功渡过最后一座($$$n$$$ 号)关口,所花费总时间(包含航行时间与所有等待时间)的数学期望是多少?
本题一个测试点内包含多组测试用例。
第一行输入一个整数 $$$T$$$ $$$(1\le T\le 10^5)$$$ 表示测试用例的个数。对于每组测试用例:
第一行输入两个整数 $$$n,k$$$ $$$(2\le n\le 2\times 10^5,\ 1\le k\le 10^9)$$$ 分别表示关口数量和每座关口的状态切换时长。
第二行输入 $$$n-1$$$ 个整数 $$$t_2,\dots ,t_n$$$ $$$(1\le t_i\le 10^9)$$$ 表示竹筏在相邻两座关口之间的通行时间。
保证所有测试用例的 $$$n$$$ 之和不超过 $$$2\times 10^5$$$。
对于每个测试用例,输出一行实数表示花费总时间的数学期望,如果您的答案与标准答案的相对误差或绝对误差不超过 $$$10^{-9}$$$ ,则认为您的答案是正确的。
具体来说,假设您的答案是 $$$a_i$$$,标准答案是 $$$b_i$$$,则当且仅当 $$$\displaystyle \frac{|a_i-b_i|}{\max(1,|b_i|)}\le 10^{-9}$$$ 时,您的答案才会被接受。
24 279 2 106 513 3 16 6 10
27.750000000 50.750000000