问题描述:

在1~N这N个数中,等概率地选取两个数l、r,如果l>r,则交换l、r。把信号中的第l个数到第r个数取出来,构成一个数列P。

A部分对话的密码是数列P的xor和的数学期望,B部分对话的密码是数列P的and和的期望,C部分对话的密码是数列P的or和的期望。你需要求出A,B,C三部分对话的密码。

输入:

第一行一个正整数N
第二行N个自然数

输出:

一行三个实数,分别表示xor和、and和、or和的期望,四舍五入保留3位小数

思路:

比较考验思维的一道题呢。因为操作都是位运算,所以我们可以分别考虑每一位的期望值,从而计算出对答案的贡献。我们把这$n$个数的第$i$位拿出来存在数组$b$中,$b[k]$就是第$k$个数的第$i$位。

一共有$n^2$种情况,选出长度为1区间的概率为$1/n^2$,选出其余区间的概率为$2/n^2$。我们可以先统计长度为1区间对答案的贡献,再计算其余区间的贡献。因为有三种操作,所以我们要对每一种操作分别计算:

  1. and操作:这个比较简单,我们从左到右枚举右端点,用last记录上一次0的出现位置。那么以$r$为右端点and值为1的区间有$(r-last-1)$个,然后乘上概率,再求和就可以求出这这一位的期望了。

  2. or操作:这个和上一个类似也比较容易,用last记录上一次1的出现位置。如果位置$r$的数为1,就有$r-1$个区间or值为1;如果位置为$r$为0,就有$last$个区间为1,不要忘了乘上概率。

  3. xor操作:这个稍微复杂,我们先前缀异或一下,然后分别记录位置$r$前前缀异或值的数量记为$cnt[0],cnt[1]$。设位置$r$的前缀异或值为$c[r]$,那么xor值为1的区间就有$cnt[c[r]^1]$个。类似的,我们也可以算出期望。

最后,我们对每一位对期望就一个和就可以算出答案了。

代码:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define LL long long
#define INF 1e18
#define LB long double
#define MAXN 2000005
using namespace std;

int n, a[MAXN], b[MAXN], c[MAXN];
LL ans[4];

LL getxor()
{
    LL sum=0, cnt[2]={0};
    memcpy(c, b, sizeof(b));
    for(int i=1; i<=n; i++) sum+=c[i];
    for(int i=1; i<=n; i++)
    {
        c[i]^=c[i-1];
        sum+=2*cnt[c[i]^1];
        cnt[c[i-1]]++;
    }
    return sum;
}

LL getand()
{
    LL sum=0, last=0;
    for(int i=1; i<=n; i++) sum+=b[i];
    for(int i=1; i<=n; i++)
    {
        if(b[i]==0) last=i;
        else sum+=2*(i-last-1);
    }
    return sum;
}

LL getor()
{
    LL sum=0, last=0;
    for(int i=1; i<=n; i++) sum+=b[i];
    for(int i=1; i<=n; i++)
    {
        if(b[i]==0) sum+=2*last;
        else sum+=2*(i-1), last=i;
    }
    return sum;
}

int main()
{
    scanf("%d", &n);
    for(int i=1; i<=n; i++) scanf("%d", &a[i]);
    for(int i=0; i<=30; i++)
    {
        for(int j=1; j<=n; j++) b[j]=(a[j]>>i)&1;
        ans[1]+=getxor()*(1<<i);
        ans[2]+=getand()*(1<<i);
        ans[3]+=getor()*(1<<i);
    }
    printf("%.3Lf %.3Lf %.3Lf", (LB)ans[1]/(1LL*n*n), (LB)ans[2]/(1LL*n*n), (LB)ans[3]/(1LL*n*n));
}

发表评论

邮箱地址不会被公开。 必填项已用*标注