E -- Expected value of the expression
DESCRIPTION
You are given an expression: A0O1A1O2A2⋯OnAnA0O1A1O2A2⋯OnAn, where Ai(0≤i≤n)Ai(0≤i≤n) represents number, Oi(1≤i≤n)Oi(1≤i≤n) represents operator. There are three operators, &,|,^&,|,^, which means and,or,xorand,or,xor, and they have the same priority.
The ii-th operator OiOi and the numbers AiAi disappear with the probability of pipi.
Find the expected value of an expression.
INPUT
The first line contains only one integer n(1≤n≤1000)n(1≤n≤1000). The second line contains n+1n+1 integers Ai(0≤Ai<220)Ai(0≤Ai<220). The third line contains nn chars OiOi. The fourth line contains nn floats pi(0≤pi≤1)pi(0≤pi≤1).
OUTPUT
Output the excepted value of the expression, round to 6 decimal places.
SAMPLE INPUT
2
1 2 3
^ &
0.1 0.2
SAMPLE OUTPUT
2.800000
HINT
Probability = 0.1 * 0.2 Value = 1 Probability = 0.1 * 0.8 Value = 1 & 3 = 1 Probability = 0.9 * 0.2 Value = 1 ^ 2 = 3 Probability = 0.9 * 0.8 Value = 1 ^ 2 & 3 = 3 Expected Value = 0.1 * 0.2 * 1 + 0.1 * 0.8 * 1 + 0.9 * 0.2 * 3 + 0.9 * 0.8 * 3 = 2.80000
题意：
给你一个n+1个数进行位操作
给你这个n+1个数(a0~an)和 进行的操作(异或，并，或) c[i]
ci 和 ai同时消失的 概率是 pi
求最后值得期望
题解：
dp[i][25][0/1]
表示前i个 数 0~21位上每一位存在（0/1）的概率，强推过去就行了
#include<bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:102400000,102400000")
#define ls i<<1
#define rs ls | 1
#define mid ((ll+rr)>>1)
#define pii pair<int,int>
#define MP make_pair
typedef long long LL;
const long long INF = 1e18+1LL;
const double pi = acos(-1.0);
const int N = 5e3+, M = 1e3+,inf = 2e9; int n,a[N];
char c[N];
double dp[N][][],p[N];
int main() {
while(scanf("%d",&n)!=EOF) {
for(int i = ; i <= n; ++i) {
scanf("%d",&a[i]);
}
memset(dp,,sizeof(dp));
for(int i = ; i <= n; ++i) {
getchar();
scanf("%c",&c[i]);
}
for(int i = ; i <= n; ++i) {
scanf("%lf",&p[i]);
}
for(int i = ; i <= ; ++i) {
if(((<<i)&a[])) dp[][i][] = ,dp[][i][] = ;
else dp[][i][] = ,dp[][i][] = ;
}
for(int i = ; i <= n; ++i) { for(int j = ; j <= ; ++j) {
dp[i][j][] += 1.0*dp[i-][j][] * p[i];
dp[i][j][] += 1.0*dp[i-][j][] * p[i];
}
for(int j = ; j <= ; ++j) {
int tmp = ((a[i]>>j)&);
if(c[i] == '^') {
dp[i][j][tmp^] += 1.0*dp[i-][j][]*(1.0-p[i]);
dp[i][j][tmp^] += 1.0*dp[i-][j][]*(1.0-p[i]);
}
else if(c[i] == '&'){
dp[i][j][tmp&] += 1.0*dp[i-][j][]*(1.0-p[i]);
dp[i][j][tmp&] += 1.0*dp[i-][j][]*(1.0-p[i]);
}
else if(c[i] == '|') {
dp[i][j][tmp|] += 1.0*dp[i-][j][]*(1.0-p[i]);
dp[i][j][tmp|] += 1.0*dp[i-][j][]*(1.0-p[i]);
}
}
}
double ans = ;
for(int i = ; i <= ; ++i) {
LL tmp = <<i;
ans += (double)(dp[n][i][]) * 1.0 * tmp;
}
printf("%.6f\n",ans);
}
return ;
}