hdu - 4649 - Professor Tian

——>>操作數的范圍 < 2^20，在暗示著此題用位運算——每個操作數可化為最多20位的二進制數，求出n+1個數的運算後每一個二進制位出現1的概率（出現0的概率不用求，若這一位是0，那麼總數的大小與這一位無關，只是占位作用）。

設a[i][j]表示第i個數的第j個二進制位；p[i][j]表示對於二進制位的第bit位，前i個數運算後得到j的概率（j為0或1）；d[i]表示這n+1個數運算後第i個二進制位出現1的概率。

對於p[i][j]，狀態轉移方程如下：

p[i][1] = p[i-1][1] * P[i] + 各種運算產生的概率。

p[i][0] = 1 - p[i][1]。

#include <cstdio>

using namespace std;

const int maxn = 200 + 3;
const int maxm = 20 + 3;
int A[maxn], a[maxn][maxm], n;
char O[maxn];
double P[maxn], p[maxn][2], d[maxm];

void read(){
    int i;
    for(i = 0; i < n+1; i++) scanf("%d", &A[i]);
    for(i = 1; i <= n; i++){
        getchar();
        O[i] = getchar();
    }
    for(i = 1; i <= n; i++) scanf("%lf", &P[i]);
}

void init(){
    int i, j;
    for(i = 0; i < n+1; i++)
        for(j = 0; j < 20; j++) a[i][j] = (1 << j) & A[i];
}

void dp(){
    int i, bit;
    for(bit = 0; bit < 20; bit++){
        if(a[0][bit]){
            p[0][1] = 1;
            p[0][0] = 0;
        }
        else{
            p[0][0] = 1;
            p[0][1] = 0;
        }
        for(i = 1; i < n+1; i++){
            p[i][1] = p[i-1][1] * P[i];
            switch(O[i]){
                case '&':{
                    if(a[i][bit]) p[i][1] += p[i-1][1] * (1 - P[i]);
                    break;
                }
                case '|':{
                    if(a[i][bit]) p[i][1] += 1 - P[i];
                    else p[i][1] += p[i-1][1] * (1 - P[i]);
                    break;
                }
                case '^':{
                    if(a[i][bit]) p[i][1] += p[i-1][0] * (1 - P[i]);
                    else p[i][1] += p[i-1][1] * (1 - P[i]);
                    break;
                }
            }
            p[i][0] = 1 - p[i][1];
        }
        d[bit] = p[n][1];
    }
}

double solve(){
    double ret = 0;
    for(int i = 0; i < 20; i++) ret += (1 << i) * d[i];
    return ret;
}

int main()
{
    int kase = 1;
    while(scanf("%d", &n) == 1){
        read();
        init();
        dp();
        printf("Case %d:\n%.6lf\n", kase++, solve());
    }
    return 0;
}