variance 题解

Galex · 2023-02-22 21:02:43 · 题解

先考虑简化所求答案：

对与原序列的 m=\large\frac{n(n+1)}2 个区间，设区间按位或的值为 o_1,o_2,\dots,o_m，对应的按位异或的值为 x_1,x_2,\dots,x_m，则每个区间的 f 值为 f_i=o_i+x_i\kern{3pt} (i=1,2,\dots,m)，所求答案即为 f_1,f_2,\dots,f_m 这 m 个数的方差的 m^2 倍 \kern{1pt}\mathrm {mod}\kern{3pt} 998244353 的值。

设这 m 个数的平均数为 \bar{f}=\frac{1}{m}\sum_{i=1}^{m}f_i，方差为 s^2=\frac{1}{m}\sum_{i=1}^m(f_i-\bar{f})^2，考虑简化所求答案 m^2s^2：

又由 f_i=o_i+x_i，有：

所以答案可转化为求各个区间五部分和：

首先考虑仅与 o_i 相关的 A,D：

一种暴力的方法是：对于每个左端点 l，初始化区间按位或和为 o=0。接下来右端点 r 依次遍历 l,l+1,\dots,n，每次遍历到新的 r 就将 o 赋值为 o\vee a_r，就得到了区间 [l,r] 对应的按位异或和，分别累加 o 和 o^2 即可。

仔细考虑整个过程，可以发现 o 的变化是存在约束的。详细地说，在二进制下，o 不断按位或并赋值的过程中，o 中已经为 1 的二进制位不会变为 0，只有仍然为 0 的位可能在某次按位或后变成 1，并保留到当前左端点处理完。这么看来在 n 较大时，o 在右端点遍历过程中很多时候是不变的。具体地描述 o 的改变次数，设 a 的值域为 V，每次改变会使 o 二进制下 0 的个数至少减少 1（由于位运算特点，此处包括以下讨论只考虑每个数二进制下最低的 \lceil\log V\rceil+1 位），所以对于一个左端点，o 的改变次数至多为 \lceil\log V\rceil+1 次。据此对右端点分段，可得到 O(\log V) 段。每段中 o 为定值，则对于 A,D 的贡献易求。

接下来考虑仅与 x_i 相关的 C,E：

按位异或没有上述按位或的性质，但区间按位异或可以用异或前缀和转化为两个数的异或。

设 s_i=a_1\oplus a_2\oplus\dots\oplus a_i，特别地，s_0=0。则对于区间 [l,r]，a_l\oplus a_{l+1}\oplus\dots\oplus a_r=s_{l-1}\oplus s_r。

仍然固定左端点 l。设 \mathrm{bit}(x,i)\in \{0,1\} 为自然数 x 二进制下从低至高第 i 位（从 0 开始）上的值，则对于每个位数 i 和右端点 r，若 \mathrm{bit}(s_{l-1}, i)\oplus \mathrm{bit}(s_r,i)=1，会对 E 产生 2^i 的贡献。进一步地，若有 \mathrm{cnt}1_{i,j}（其中 0\leq i\leq\lceil\log{V}\rceil,j\in\{0,1\}） 个右端点 r 满足 l\leq r\leq n 且 \mathrm{bit}(s_r,i)=j，那么左端点 l 对 E 的贡献为 \sum_{i=0}^{\lceil\log{V}\rceil}2^i\times \mathrm{cnt}1_{i,\mathrm{bit}(s_{l-1},i)\oplus1}。

固定左端点 l，并将右端点按照按位或的性质分段。设右端点 r 在 i\leq r\leq j 的区间中，所得区间 [l,r] 按位或的值都是 o，则这段的贡献为 \sum 2o_kx_k=2o\sum x_k（即提出固定的 2o，不写出确切的上下界）。\sum x_k 仍考虑按二进制位计算贡献。设 1,2,...,k 中有 \mathrm{cnt}3_{k,u,v} 个位置 x 满足 \mathrm{bit}(s_x,u)=v，则固定的 l 与 i\leq r\leq j 的 r 对 B 的贡献为 2o\sum_{k=0}^{\lceil\log{V}\rceil}2^i\times(\mathrm{cnt}3_{j-1,\mathrm{bit}(s_{l-1},k)\oplus1}-\mathrm{cnt}3_{i-1,\mathrm{bit}(s_{l-1},k)\oplus1})。