2016 ICPCCamp第3日：中国大奖赛-随机算术动态规划问题？

本文共计827个文字，预计阅读时间需要4分钟。

题目：已知n个数，每次等概随机选取2个数，等概相加或相乘，并用这个数替代所选取的2个数，直到只剩一个数为止，问期望值。

两个数的情形为：x, y，则ans=x + y + xy^2。显然对于a1, a2, ..., an而言，

题意：已知n个数，每次等概率随机选取2个数，等概率相加或相乘，并用这个数代替所取的2个数，直到只剩一个数为止，问该数期望。

2个数的情况 x,y
ans=x+y+xy2

显然对于a1,a2,…,an而言，答案为∑Lf(n,i)al1al2…ali 其中L为A的任意子集，其中的元素为l1,l2,…,ln,f(n,i)为只与|A|,|L|有关函数。

那么现在可以递归求f(n,i)
假设w1,w2是L中2元素,x,y是不在L中的2元素，则有4种情况。