思路：反状态压缩——把数据转换成20位的01来进行运算
因为只有20位，而且&,|,^都不会进位，那么一位一位地看，每一位不是0就是1，这样求出每一位是1的概率，再乘以该位的十进制数，累加，就得到了总体的期望。
对于每一位，状态转移方程如下：
f[i][j]表示该位取前i个数，运算得到j(0或1)的概率是多少。
f[i][1]=f[i-1][1]*p[i]+根据不同运算符和第i位的值运算得到1的概率。
f[i][0]=f[i-1][0]*p[i]+根据不同运算符和第i位的值运算得到0的概率。
初始状态：f[0][0~1]=0或1（根据第一个数的该位来设置）
每一位为1的期望 f[n][1]
这题只要知道怎样表示状态就很简单了！！！以上是标程……
代码如下：
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<vector>
#define ll __int64
#define pi acos(-1.0)
#define MAX 50000
using namespace std;
double dp[][],p[];
char str[];
int f[];
double fun1(int i,int j){//位运算结果为1的期望值
double ans=0.0,pp=-p[i];
int t=(f[i]>>j)&;
if(str[i]=='&'&&t){
ans=dp[i-][]*pp;
}
else if(str[i]=='|'){
ans=dp[i-][]*pp;
if(t==)
ans+=dp[i-][]*pp;
}
else if(str[i]=='^'){
if(t==)
ans=dp[i-][]*pp;
else ans=dp[i-][]*pp;
}
return ans;
}
double fun0(int i,int j){//位运算结果为0的期望值
double ans=0.0,pp=-p[i];
int t=(f[i]>>j)&;
if(str[i]=='&'){
if(t==)
ans=dp[i-][]*pp;
else ans=(dp[i-][]+dp[i-][])*pp;
}
else if(str[i]=='|'&&t==)
ans=dp[i-][]*pp;
else if(str[i]=='^'){
if(t==) ans=dp[i-][]*pp;
else ans=dp[i-][]*pp;
}
return ans;
}
int main(){
int c,n,i,j,k=;
double ans;
while(scanf("%d",&n)!=EOF){
for(i=;i<=n;i++) scanf("%d",&f[i]);
for(i=;i<=n;i++) scanf("%s",&str[i]);
for(i=;i<=n;i++) scanf("%lf",&p[i]);
ans=0.0;
for(i=;i<;i++){
c=(f[]>>i)&;
dp[][]=c; dp[][]=c^;
for(j=;j<=n;j++){
dp[j][]=dp[j-][]*(p[j])+fun1(j,i);
dp[j][]=dp[j-][]*(p[j])+fun0(j,i);
}
ans+=(<<i)*dp[n][];
}
printf("Case %d:\n%.6lf\n",++k,ans);
}
return ;
}