二进制位最后出现1的概率 - c++编程基础

    思路：每个数取他的二进制位，对于每一位，我们求他最后出现1的概率，那么最后的期望就是为1的概率乘以该位的十进制数，累加即可。
    想到状压就是水题…
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <string>
    #include <cmath>
    #include <cstring>
    #include <queue>
    #include <set>
    #include <vector>
    #include <stack>
    #include <map>
    #include <iomanip>
    #define PI acos（-1.0）
    #define Max 2505
    #define inf 0x7fffffff
    #define LL（x）（ x 《 1 ）
    #define RR（x）（ x 《 1 | 1 ）
    #define REP（i,s,t） for（ int i = （ s ） ; i <= （ t ） ; ++ i ）
    #define ll long long
    #define mem（a,b） memset（a,b,sizeof（a））
    #define mp（a,b） make_pair（a,b）
    #define PII pair<int,int>
    #define bug puts（"here"）
    using namespace std;
    #define N 222
    double dp[22][N] ;//第i位第j个数是k的概率。
    int a[N] ;
    char b[N] ;
    double p[N] ;
    int n ;
    int main（） {
    int ca = 0 ;
    while（cin 》 n）{
    for （int i = 0 ; i <= n ; i ++ ）{
    scanf（"%d",&a[i]） ;
    }
    for （int i = 1 ; i <= n ; i ++ ）{
    cin 》 b[i] ;
    }
    for （int i = 1 ; i <= n ; i ++ ）{
    cin 》 p[i] ;
    }
    for （int i = 0 ; i <= n ; i ++ ）{
    for （int j = 0 ; j <= 20 ; j++ ）{
    for （int k = 0 ;k < 2 ; k ++ ）

    dp[j][i][k] = 0 ;
    }
    }
    double ans = 0 ;
    for （int i = 0 ; i <= 20 ; i ++ ）{
    if（a[0] & （1 《 i））
    dp[i][0] = 1 ;
    else dp[i][0][0] = 1 ;
    for （int j = 1 ; j <= n ; j ++ ）{
    dp[i][j] = dp[i][j - 1] * p[j] ;//该位不取
    dp[i][j][0] = dp[i][j - 1][0] * p[j] ;//该位不取
    if（a[j] & （1 《 i））{//取该位
    if（b[j] == '&'）{
    dp[i][j] += dp[i][j - 1] * （1 - p[j]） ;
    dp[i][j][0] += dp[i][j - 1][0] * （1 - p[j]） ;
    }
    else if（b[j] == '|'）{
    dp[i][j] += dp[i][j - 1] * （1 - p[j]） ;
    dp[i][j] += dp[i][j - 1][0] * （1 - p[j]） ;
    }
    else {
    dp[i][j] += dp[i][j - 1][0] * （1 - p[j]） ;
    dp[i][j][0] += dp[i][j - 1] * （1 - p[j]） ;
    }
    }
    else {//同理
    if（b[j] == '&'）{
    dp[i][j][0] += dp[i][j - 1] * （1 - p[j]） ;
    dp[i][j][0] += dp[i][j - 1][0] * （1 - p[j]） ;
    }
    else if（b[j] == '|'）{
    dp[i][j] += dp[i][j - 1] * （1 - p[j]） ;
    dp[i][j][0] += dp[i][j - 1][0] * （1 - p[j]） ;
    }
    else {
    dp[i][j][0] += dp[i][j - 1][0] * （1 - p[j]） ;
    dp[i][j] += dp[i][j - 1] * （1 - p[j]） ;
    }
    }
    }
    ans += （1 《 i） * dp[i][n] ;
    }
    printf（"Case %d:\n%.6f\n",++ca ,ans） ;
    }
    return 0 ;
    }