暴力水过的,比赛的时候T了两次,优化一下初始化,终于水过了。
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
#define MOD 1000000007
#define LL __int64
double dp[][<<];
int que[<<];
int flag[<<];
double o[];
char str[];
int p[];
int judge(char s)
{
if(s == '^')
return ;
else if(s == '&')
return ;
else if(s == '|')
return ;
return ;
}
int main()
{
int n,cas = ,i,j,x,t1,t2,num,tnum;
while(scanf("%d",&n)!=EOF)
{
scanf("%d",&x);
for(i = ;i <= n;i ++)
scanf("%d%*c",&p[i]);
for(i = ;i <= n;i ++)
scanf("%c%*c",&str[i]);
for(i = ;i <= n;i ++)
scanf("%lf",&o[i]);
flag[x] = ;
num = ;
que[] = x;
dp[][x] = 1.0;
t1 = ;t2 = ;
for(i = ;i <= n;i ++)
{
tnum = num;
for(j = ;j <= num;j ++)
{
dp[t2][que[j]] += dp[t1][que[j]]*o[i];
int temp,z = judge(str[i]);
if( z == )
{
temp = que[j]^p[i];
if(!flag[temp])
{
flag[temp] = ;
que[++tnum] = temp;
}
dp[t2][temp] += dp[t1][que[j]]*(1.0-o[i]);
}
else if(z == )
{
temp = que[j]&p[i];
if(!flag[temp])
{
flag[temp] = ;
que[++tnum] = temp;
}
dp[t2][temp] += dp[t1][que[j]]*(1.0-o[i]);
}
else
{
temp = que[j]|p[i];
if(!flag[temp])
{
flag[temp] = ;
que[++tnum] = temp;
}
dp[t2][temp] += dp[t1][que[j]]*(1.0-o[i]);
}
}
num = tnum;
swap(t2,t1);
for(j = ;j <= num;j ++)
dp[t2][que[j]] = 0.0;
}
double ans = ;
for(i = ;i <= num;i ++)
{
ans += que[i]*dp[t1][que[i]];
flag[que[i]] = ;
dp[t1][que[i]] = 0.0;
}
printf("Case %d:\n%.6f\n",cas++,ans);
}
return ;
}