Rainbow的信号位运算的递推

程智明

2023-12-01

Rainbow 的信号

Freda 发明了传呼机之后，rainbow进一步改进了传呼机发送信息所使用的信号。由于现在是数字、信息时代，rainbow发明的信号用N个自然数表示。为了避免两个人的对话被大坏蛋Variant F偷听T_T，rainbow把对话分成A、B、C三部分，分别用a、b、c三个密码加密。现在Freda接到了rainbow的信息，她的首要工作就是解密。Freda了解到，这三部分的密码计算方式如下：
在1~N这N个数中，等概率地选取两个数l、r，如果l>r，则交换l、r。把信号中的第l个数到第r个数取出来，构成一个数列P。
A部分对话的密码是数列P的xor和的数学期望值。xor和就是数列P中各个数异或之后得到的数；xor和的期望就是对于所有可能选取的l、r，所得到的数列的xor和的平均数。
A部分对话占接收到的信息总量的40%，因此如果你计算出密码a，将获得该测试点40%的分数。
B部分对话的密码是数列P的and和的期望，定义类似于xor和，占信息总量的30%。
C部分对话的密码是数列P的or和的期望，定义类似于xor和，占信息总量的30%。
第一行一个正整数 N。
Input
第二行N个自然数，表示Freda接到的信号。
Output
一行三个实数，分别表示xor和、and和、or和的期望，四舍五入保留3位小数，相邻两个实数之间用不少于一个空格隔开。三个实数分别占该测试点40%、30%、30%的分数，如果你的输出少于三个实数，或者你的输出不合法，将被判0分。
Sample Input
2
4 5
Sample Output
2.750 4.250 4.750
Sample Input 2
3
1 0 1
Sample Output2
0.667 0.222 0.889
Tip
Sample 1 共包含四种可能的l、r：
l, r xor和 and和 or和
1,1 4 4 4
1,2 1 4 5
2,1 1 4 5
2,2 5 5 5
以上每一对l、r出现的概率均相同，因此分别对xor和、and和、or和取平均数就是数学期望值。
Data Constraint
对于20%的数据，1≤N≤100。
对于40%的数据，1≤N≤1000。
对于另外30%的数据，N个数为0或1。
对于100%的数据，1≤N≤100000，N 个自然数均不超过 10⁹。

观察本题，我们发现，题目中，要求我们对所有的[l,r]范围的队列进行求xor和，and和，or和。
那么，如果选择直接枚举任意的 l,r 在 [1,N] 内，来逐个逐个求值，很显然是行不通的。
当然，由于xor值得特殊性，如果有f[x]表示[1,x]范围内的 xor和，那么我们可以求出任意的区间 [a,b] xor和是 (f[b] xor f[a-1])，但是，这种做法的复杂度很显然复杂度还在N²，仍然不可取，所以我们进一步思考。
因为，这道题有一个值得注意的地方，它要求我们求[l,r]的xor和，and和，or和，而这些处理都是位运算，换句话说，我们所有的处理只需要对一个数的每一位进行处理就可以了。
所以，我们就对所有数的同一个位进行处理。当然，我们处理数据的时候不能够逐个位的处理，而是选择处理一个数的所有位并记录下来，轮到下一个数对应所有位进行同样的处理。
那么，我们可以很快知道，如果可以知道，在我们枚举区间右端点r时，记录下它最后运算结果为1的情况数，复杂度就可以骤降为 O(βN) (β是数的位数)

对于and和来说，如果这个位是0，那么，这个数运算and结果为1的可能就是0；如果这个位是1，那么这个数运算and结果为1的区间有之前的那个数运算结果为1的区间的个数+1（也就是它自己这个区间本身）
对于or和来说，如果这个位是0，那么这个数运算or结果为1的区间数就是它之前的数的运算结果为1的区间数。如果这个位是1，那么这个数运算or结果为1的区间数就是它是第几个数。（也就是说，l<r时，l取任何数运算or得到的值都是1）
对于xor和来说，如果这个位是0，那么直接继承上一个数的答案；如果这个位是1，那么反转上一个数答案（1 xor 1 = 0 ，1 xor 0 = 1），并且将运算结果为1的区间数+1（也就是它自己这个区间本身）

所以，我们就可以通过这些位运算的性质，写出这三个相应的递推方程，并得到复杂度大概是O(N)的代码，代码如下。

#include <cstdio>
#include <math.h>
 
#define LL long long 
 
using namespace std;
 
const int maxn=100010;
int n,r;
int xo[maxn][32][2],an[maxn][32],o[maxn][32];
double a,b,c;
LL s;
 
inline int read()
{
    int x=0;char c=getchar();
    while ((c<'0')||(c>'9'))
        c=getchar();
    while ((c>='0')&&(c<='9'))
        x=(x<<3)+(x<<1)+c-'0',c=getchar();
    return x;
}
 
int main()
{
    n=read();
    for (int i=1;i<=n;i++)
    {
        r=read();
        s+=r;
        for (int j=1,now=1;j<=30;now<<=1,j++)
        {
            if (now&r)
            {
                xo[i][j][0]=xo[i-1][j][1];
                xo[i][j][1]=xo[i-1][j][0]+1;
                an[i][j]=an[i-1][j]+1;
                o[i][j]=i;
                a+=(double)((((LL)xo[i][j][1]-1)*(LL)now)<<1)/((LL)n*n);
                b+=(double)((((LL)an[i][j]-1)*(LL)now)<<1)/((LL)n*n);
                c+=(double)((((LL)o[i][j]-(LL)1)*(LL)now)<<1)/((LL)n*n);
            }
            else
            {
                xo[i][j][0]=xo[i-1][j][0]+1;
                xo[i][j][1]=xo[i-1][j][1];
                an[i][j]=0;
                o[i][j]=o[i-1][j];
                a+=(double)(((LL)xo[i][j][1]*(LL)now)<<1)/((LL)n*n);
                c+=(double)(((LL)o[i][j]*(LL)now)<<1)/((LL)n*n);
            }
        }
    }
    a+=((double)s/((LL)n*n));b+=((double)s/((LL)n*n));c+=((double)s/((LL)n*n));
    a=(double)(round(a*1000))/1000;
    b=(double)(round(b*1000))/1000;
    c=(double)(round(c*1000))/1000;
    printf("%.3lf %.3lf %.3lf",a,b,c);
    return 0;
}

Rainbow的信号位运算的递推