這題起初沒讀懂題意，悲劇啊，然後看了題解寫完就AC了
題意是給一個N，然後給N+1個整數 接著給N個操作符（只有三種操作 即 或 ，與 ，和異或 | & ^ ）這樣依次把操作符插入整數之間就可以得到一個表達式
接著給出 N 給浮點數（在0~1之間表示概率 ）表示的是 操作符和他右邊的整數丟失的概率。 例如下面這組數據
1
1 2
&
0.5
整數與操作符間可以組成一個表達式即 1&2 但是由於某些原因表達式的操作符和他操作的右邊的
那個數有一定的概率會丟失這組數據就是 &2有 0.5的概率會丟失 ，要你算這個表達式的期望值是
多少 這組數據可以這樣算 當&2不丟失的時候1&2=0
當他丟失的時候表達式就變成了1 這樣這個表達式的期望值就是 0*0.5+1*0.5=0.5 ；
貌似沒思路啊。。。。
思路如下：
先反狀態壓縮——把數據轉換成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[0][0~1]=0或1（根據第一個數的該位來設置）
每一位為1的期望 f[n][1]
最後的結果就是把每一位為一的概率乘上這位的位權相加就可以了
下面是我的代碼：
#include<cstdio>
#include<bitset>
#include<iostream>
using namespace std;
bitset<20> team[205];//強烈推薦用bitset，這個比較快而且簡單好用，關鍵還省空間
char ch[205];
int pow[20],n,cas=0;
double p[205], dp[20][205][2];
int cal(int i,char c,int j,int f=0)//f=0表示 默認是計算通過運算為0的概率，f=1則是去計算為1的概率
{//這個函數計算的運算結果概率只能是1或0，所以可以返回真假值
int ans;
if(c=='&') ans=i&j;
if(c=='^') ans=i^j;
if(c=='|') ans=i|j;
if(!f) return ans==0;//返回通過計算為0的概率
else return ans==1;//返回通過計算1的概率
}
int read()
{
if(!(cin>>n)) return 0;//沒有讀入了就返回假值
for(int a,i=0;i<=n;i++)
{
cin>>a;
team[i]=a;//用bitset轉化為二進制
}
for(int i=0;i<n;i++)
cin>>ch[i];//讀操作符
for(int i=0;i<n;i++)
cin>>p[i];//讀概率
return 1;
}
void deal()
{
double ans=0;
for(int i=0;i<20;i++)//初始化第一位的概率
if(team[0][i]) dp[i][0][1]=1,dp[i][0][0]=0;
else dp[i][0][1]=0,dp[i][0][0]=1;
for(int i=0;i<20;i++)
for(int j=1;j<=n;j++)
{
dp[i][j][1]=dp[i][j-1][1]*p[j-1]+(1-p[j-1])*(dp[i][j-1][0]*cal(0,ch[j-1],team[j][i],1)+dp[i][j-1][1]*cal(1,ch[j-1],team[j][i],1));//這個dp式如果還不懂就看一下，文章尾部我的說明。。
//計算當前為1的概率
dp[i][j][0]=dp[i][j-1][0]*p[j-1]+(1-p[j-1])*(dp[i][j-1][0]*cal(0,ch[j-1],team[j][i])+dp[i][j-1][1]*cal(1,ch[j-1],team[j][i]));
//計算當前為0的概率 和為1的概率是一回事的
}
for(int i=0;i<20;i++)
ans+=pow[i]*dp[i][n][1];//統計結果
printf("Case %d:\n",++cas);
printf("%.6lf\n",ans);
}
int main()
{
for(int i=pow[0]=1;i<20;i++)
pow[i]=pow[i-1]*2;//計算二進制的位權
while(read()) deal();
return 0;
}
dp[i][j][1]=dp[i][j-1][1]*p[j-1]+(1-p[j-1])*(dp[i][j-1][0]*cal(0,ch[j-1],team[j][i],1)+dp[i][j-1][1]*cal(1,ch[j-1],team[j][i],1));
其中dp[i][j][1]表示前j個操作後使第i位變成1的概率，dp[i][j-1][1]*p[j-1]，表示當前的操作符和其右邊的數消失後，使這位為1的概率
(1-p[j-1])*(dp[i][j-1][0]*cal(0,ch[j-1],team[j][i],1)+dp[i][j-1][1]*cal(1,ch[j-1],team[j][i],1));這整串是在算當前的操作符和其右邊的數不消失的概率，所以有公因子(1-p[j-1])即表示，表達式不消失的概率，dp[i][j-1][0]*cal(0,ch[j-1],team[j][i],1)這句是在算如果上一步當前這位計算的結果是0，那麼通過這步運算得到1的概率
，dp[i][j-1][0] 這是上一步算出這位結果為0的概率，cal(0,ch[j-1],team[j][i],1)這是算0和當前的操作符及其右邊的數進行運算為1的概率，這個概率要麼是一要麼是0，dp[i][j-1][1]*cal(1,ch[j-1],team[j][i],1)這句就是算若上次運算的結果是1那麼和當前這一步運算後得到的是1的概率，終於說完這個惡心的式子了。。。下面那個算0的式子就可以對應的去理解了，即dp[i][j][0]=dp[i][j-1][0]*p[j-1]+(1-p[j-1])*(dp[i][j-1][0]*cal(0,ch[j-1],team[j][i])+dp[i][j-1][1]*cal(1,ch[j-1],team[j][i]));
再附一個沒有注釋的代碼
#include<cstdio>
#include<bitset>
#include<iostream>
using namespace std;
bitset<20> team[205];
char ch[205];
int pow[20],n,cas=0;
double p[205];
double dp[20][205][2];
int cal(int i,char c,int j,int f=0)
{
int ans;
if(c=='&') ans=i&j;
if(c=='^') ans=i^j;
if(c=='|') ans=i|j;
if(!f) return ans==0;
else return ans==1;
}
int read()
{
if(!(cin>>n)) return 0;
for(int a,i=0;i<=n;i++)
{
cin>>a;
team[i]=a;
}
for(int i=0;i<n;i++)
cin>>ch[i];
for(int i=0;i<n;i++)
cin>>p[i];
return 1;
}
void deal()
{
double ans=0;
for(int i=0;i<20;i++)
if(team[0][i]) dp[i][0][1]=1,dp[i][0][0]=0;
else dp[i][0][1]=0,dp[i][0][0]=1;
for(int i=0;i<20;i++)
for(int j=1;j<=n;j++)
{
dp[i][j][1]=dp[i][j-1][1]*p[j-1]+(1-p[j-1])*(dp[i][j-1][0]*cal(0,ch[j-1],team[j][i],1)+dp[i][j-1][1]*cal(1,ch[j-1],team[j][i],1));
dp[i][j][0]=dp[i][j-1][0]*p[j-1]+(1-p[j-1])*(dp[i][j-1][0]*cal(0,ch[j-1],team[j][i])+dp[i][j-1][1]*cal(1,ch[j-1],team[j][i]));
}
for(int i=0;i<20;i++)
ans+=pow[i]*dp[i][n][1];
printf("Case %d:\n",++cas);
printf("%.6lf\n",ans);
}
int main()
{
for(int i=pow[0]=1;i<20;i++)
pow[i]=pow[i-1]*2;
while(read()) deal();
return 0;
}
