位运算 UEST 84 Binary Operations

 

题目传送门

题意：所有连续的子序列的三种位运算计算后的值的和的期望分别是多少

分析：因为所有连续子序列的组数有n * (n + 1) / 2种，所以要将他们分类降低复杂度，以ai为结尾的分成一组，至于具体的做法，我觉得这篇题解已经写的很详细了，UESTC 1709 Binary Operations

吐槽一下，题解的代码交上去是TLE的，至今不知道为何，我写的是WA，将所有类型改成ll才AC。。。

 

/************************************************
* Author        :Running_Time
* Created Time  :2015/10/8 星期四 17:43:10
* File Name     :B.cpp
 ************************************************/

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <bitset>
#include <cstdlib>
#include <ctime>
using namespace std;

#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
typedef long long ll;
const int N = 5e4 + 10;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const double EPS = 1e-8;
ll a[N], num[35], s[N];

void add(int x) {
    int k = 0;
    while (x)   {
        if (x & 1)  num[k]++;
        x >>= 1;    k++;
    }
}

int main(void)    {
    ll T, cas = 0; scanf ("%d", &T);
    while (T--) {
        ll n;  scanf ("%lld", &n);
        for (int i=0; i<n; ++i)    scanf ("%lld", &a[i]);
        memset (num, 0, sizeof (num));
        memset (s, 0, sizeof (s));
        double ans1 = 0, ans2 = 0, ans3 = 0;
        ll tmp;
        for (int i=0; i<n; ++i) {
            s[i] = a[i];
            if (i == 0) add (a[i]);
            else    {
                tmp = a[i];
                for (int j=0; j<31; ++j)    {
                    if (tmp & (1 << j)) {}
                    else num[j] = 0;
                    s[i] += (num[j] * (1 << j));
                }
                add (a[i]);
            }
            ans1 += s[i];
        }
        
        memset (num, 0, sizeof (num));
        for (int i=0; i<n; ++i) {
            s[i] = a[i];
            if (i == 0) add (a[i]);
            else    {
                tmp = a[i];
                for (int j=0; j<31; ++j)    {
                    if (tmp & (1 << j)) num[j] = i;
                    s[i] += (num[j] * (1 << j));
                }
                add (a[i]);
            }
            ans2 += s[i];
        }
        
        memset (num, 0, sizeof (num));
        for (int i=0; i<n; ++i) {
            s[i] = a[i];
            if (i == 0) add (a[i]);
            else    {
                tmp = a[i];
                for (int j=0; j<31; ++j)    {
                    if (tmp & (1 << j)) num[j] = i - num[j];
                    s[i] += (num[j] * (1 << j));
                }
                add (a[i]);
            }
            ans3 += s[i];
        }
        ll len = n * (n + 1) / 2;
        printf ("Case #%lld: %.6lf %.6lf %.6lf\n", ++cas, ans1 / len, ans2 / len, ans3 / len);
    }

    return 0;
}