Rainbow的信号

桃扇骨 2022-01-08 00:23 162阅读 0赞

[Rainbow的信号][Rainbow]

有一串长度为n的数列，现在从中等概率选出l，r，如果l大于r，则交换，有三个询问

1.  l~r间的数与和的数学期望
2.  l~r间的数或和的数学期望
3.  l~r间的数异或和的数学期望

对于100%的数据，1<=n<=100000，n个自然数均不超过10^9。

### 解 ###

注意到l==r，概率为\\(1/n^2\\),其外概率均为\\(2/n^2\\),考虑到有固定的概率，考虑公式法，对于l==r显然可以暴力做,现在问题在于如何快速求出区间的二进制运算和，注意到二进制不进位的特点，考虑二进制拆分，于是对于所有数的单独的每一二进制位讨论，接着考虑如何维护区间二进制运算。

对于l!=r，于是枚举右端点r，再考虑左端点的情况，记录\\(last\[x\]\\)表示当前r左边第一个出现x的位置，显然可以维护,当前二进制位为第k位，数列为a，对于询问

#### 与运算 ####

1.  a\[r\]==0:

\\\[ans+=0\\\]

1.  a\[r\]==1:

\\\[ans+=(r-1-last\[0\])\\times 2^k\\times \\frac\{2\}\{n^2\}\\\]

#### 或运算 ####

1.  a\[r\]==0:

\\\[ans+=last\[1\]\\times 2^k\\times \\frac\{2\}\{n^2\}\\\]

1.  a\[r\]==1:

\\\[ans+=(r-1)\\times 2^k \\times \\frac\{2\}\{n^2\}\\\]

#### 异或运算 ####

注意到异或类似与奇偶的性质，于是设c1,c2分别为从r向右数的以1开头的奇数段，偶数段的长度，举个例子

00001 **0001** 000

**00001** 0001 **0001**

例子中标黑色的段为奇数段，其余为偶数段，r为最后一个数字

于是我们有

1.  a\[r\]==0:

\\\[ans+=c1\\times 2^k\\times \\frac\{2\}\{n^2\},++c2\\\]

1.  a\[r\]==1:

\\\[ans+=c2\\times 2^k\\times \\frac\{2\}\{n^2\},wap(c1,c2),++c1\\\]

不难得知时间复杂度应为\\(O(nlog(n))\\)

参考代码：

#include <iostream> #include <cstdio> #define il inline #define ri register #define lb long double #define swap(x,y) x^=y^=x^=y using namespace std; lb ans1,ans2,ans3,n1,n2; int num[100001],last[2],c1,c2; il void read(int&); int main(){ int n,i,j,sxr;read(n),n2=2/((lb)n*n),n1=n2/2; for(i=1;i<=n;++i)read(num[i]); for(i=0,sxr=1;i<31;++i,sxr<<=1) for(j=1,last[0]=last[1]=c1=c2=0;j<=n;num[j]>>=1,++j) if(num[j]&1)ans1+=c2*n2*sxr+n1*sxr,ans2+=(j-1-last[0])*n2*sxr+n1*sxr, ans3+=(j-1)*n2*sxr+n1*sxr,last[1]=j,swap(c1,c2),++c1; else ans1+=c1*n2*sxr,ans3+=last[1]*n2*sxr,last[0]=j,++c2; printf("%.3Lf %.3Lf %.3Lf",ans1,ans2,ans3); return 0; } il void read(int &x){ x&=0;ri char c;while(c=getchar(),c<'0'||c>'9'); while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar(); }

转载于:https://www.cnblogs.com/a1b3c7d9/p/10809362.html

[Rainbow]: http://contest-hunter.org:83/contest/0x30%E3%80%8C%E6%95%B0%E5%AD%A6%E7%9F%A5%E8%AF%86%E3%80%8D%E4%BE%8B%E9%A2%98/3801%20Rainbow%E7%9A%84%E4%BF%A1%E5%8F%B7