题意：已知n个数，每次等概率随机选取2个数，等概率相加或相乘，并用这个数代替所取的2个数，直到只剩一个数为止，问该数期望。 2个数的情况 x,y ans=x+y+xy2 显然对于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种情况。
- xy
- w1w2
- w1+w2
- x+w
分类讨论
#include <iostream>#include <cmath>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <functional>
#include <cstdlib>
#include <queue>
#include <stack>
using namespace std;
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
typedef long long ll;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return (a-b+llabs(a-b)/F*F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
int read()
{
int x=0,f=1; char ch=getchar();
while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
int n;
const int MAXN = ( 2000 + 10 );
ll f[MAXN][MAXN]={0};
ll pow2(ll a,ll b){
if (b==1) return a;
if (b==0) return 1;
ll t= pow2(a,b/2);
t =t *t%F;
if (b&1) t=t*a%F;
return t;
}
ll inv(ll x) {return pow2(x,F-2);}
void prework() {
Rep(i,n+1) f[i][0]=1;
For(i,n) For(x,i) { // (x,y) w
if (i==1&&x==1) {
f[1][1]=1;continue;
}
ll p1=mul(mul(mul(mul(x,i-x) , inv(i) ),inv(i-1)) ,2); //跨立
ll p2=mul(mul(mul(x,x-1) , inv(i) ),inv(i-1)) ; // 2 个里面的
ll p3=mul(mul(mul(i-x,i-x-1) , inv(i) ),inv(i-1) ) ; // 2个外面的
p1=mul(p1,inv(2));
p2=mul(p2,inv(2));
p3=mul(p3,inv(2));
if (x>=2) upd(f[i][x],mul(p2,f[i-1][x-1])); //(xy)
if (i-x>=2) upd(f[i][x],mul(p3,f[i-1][x])); //w1w2
if (i-x>=2) upd(f[i][x],mul(p3,f[i-1][x])); // w1+w2
if (i-x>=1&&x>=1) upd(f[i][x],mul(p1,f[i-1][x])); // x+w
}
}
ll S[MAXN][MAXN]={0};
ll a[MAXN];
int main() {
n=read();
prework();
For(i,n) a[i]=read();
S[0][0]=1; For(i,n) S[i][0]=1;
ll ans=0;
For(i,n) For(j,i) {
if (j>=1) upd(S[i][j],mul(S[i-1][j-1],a[i] ) );
if (i>j) upd(S[i][j], S[i-1][j] );
}
For(i,n) {
upd(ans, mul(S[n][i] , f[n][i] ));
}
cout<<ans<<endl;
return 0;
}