TouchStone
  请登录后使用
登录 注册
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P8252
  • 题目
  • P8252数字游戏
    限制 : 时间限制 : - MS   空间限制 : - KB
    评测说明 : 1s 256MB
    问题描述

    有一个由$n$个整数组成的序列$a$,其中的元素为 \(a_{1}, a_{2},..., a_{n}\)。每次从第2个元素到最后一个元素中随机等概率地选择一个元素,将这个元素的前一个元素减去这个元素的值,并把这个元素移出序列。重复上述操作直到序列$a$只剩下一个元素。问最后剩下的元素的期望值是多少。

    输入格式

    第一行包含一个整数$T \left ( 1 \leqslant T \leqslant 10000 \right )$,表示数据组数。

    接下来有$T$组数据,每组数据包含两行,其中第一行包含一个整数$n \left ( 1 \leqslant n \leqslant 20 \right )$,第二行包含$n$个整数 \(a_{1}, a_{2},..., a_{n} ( -10^{9} \leqslant a_{i} \leqslant 10^{9} )\)

    输出格式

    对于每组数据输出一行,包含一个整数,表示最后剩下的元素的期望值四舍五入后的结果。

    样例输入

    3
    3
    1 1 1
    2
    1 2
    1
    100

    样例输出

    0
    -1
    100

    提示

    对于样例中第一组测试数据,有 \(\frac{1} {2}\) 的概率第一次选中当前第2个元素,序列变为 \(\left [ 0, 1 \right]\),第二次选中当前第2个元素,最后剩下的元素值为-1;有 \(\frac{1} {2}\) 的概率第一次选中当前第3个元素,序列变为 \(\left [ 1, 0 \right]\),第二次选中当前第2个元素,最后剩下的元素值为1。因此最后剩下的元素的期望值为 \(\left ( -1 \right ) \times \frac{1} {2} + 1 \times \frac{1} {2} = 0\)