UOJ#38 玛里苟斯 题解

题面在这里

简要题意

原题已经非常非常地简要辣！细化一下数据范围：

题♂解♂

鉴于网上的题解都很神，然而这题比题解更神，我这个退役选手只能自己写一份题♂解♂造福大众辣。

首先答案的大体形式是$\displaystyle E=\frac{\sum_{i=1}^{2^n}x_i^k}{2^n}$，其中$x_i$是一些数异或出来的结果。

我们注意到一个性质，如果$S$的一个子集$A$和$a_i \not \in A$，其中满足$A$中所有元素的异或为$a_i$，那么我们可以把$a_i$删掉，而答案不改变。这是因为去掉$a_i$后，方案数除以了$2$，同时分子上的数也除以了$2$，原先每个数都与$A$中的异或和异或了一遍，又跟$a_i$异或了一遍。

但是线性基有$\mathcal{O}(\log_2a_i)$个，总的方案数也就是$\mathcal{O}(2^{\log_2a_i})=\mathcal{O}(a_i)$的，只能做$k \geqslant 3$的情况。

$k=1$

由于是线性的期望，对于这种问题我萌当然按位考虑啦。假设当前统计第$i$位的贡献，那么当且仅当这位上异或出来是$1$才有意义，也就是说在第$i$位上，选择了奇数个$1$。

设第$i$位上有$a$个数是$1$，$n-a$个数是$0$。那么这一位的贡献就是：

$\displaystyle 2^i \times 2^{n-a} \sum_{q=1}^{\lfloor \frac{a+1}{2} \rfloor} \mathrm{C}_a^{2q-1}$

其中$2^{n-a}$是因为$0$可以随便选。

什么？你没有看错！组合数奇数位置上的和不就是$2^{a-1}$嘛！于是就变成了

$\displaystyle 2^i \times 2^{n-a} \times 2^{a-1} = 2^i \times 2^{n-1}$

当然这里必须要$a>0$，否则这一位的贡献就是$0$。

于是

$\displaystyle E=\frac{\sum_{i=0}^{63}\left(2^i \times 2^{n-1} \quad | i位有1 \right)}{2^n} = \sum_{i=0}^{63}\left(2^{i-1} \quad | i位有1 \right)$

所以把所有的$a_i$用$\mathrm{or}$连接，就可以知道哪些位有$1$，答案也就是$\mathrm{or}$出来的值$\div 2$。同时，我们会发现这里如果有小数部分，只可能是$0.5$，$i=0$时特判一下即可。

时间复杂度$\mathcal{O}(n)$。

$k=2$

这个时候我萌要多讨论一下。为了延续之前的经验，我们要尝试按位统计。

把一个二进制数的每一位列出来，那么可以得到：

$\displaystyle E=\frac{\sum_{i=1}^{2^n} \left( \sum_{j=0}^{31}b_{i,j} \times 2^j \right)^2}{2^n}=\frac{\sum_{i=1}^{2^n} \left(\sum_{j=0}^{31} b_{i,j} \times 2^j\right) \left( \sum_{p=0}^{31} b_{i,p} \times 2^p \right)}{2^n} = \frac{\sum_{i=1}^{2^n} \sum_{j=0}^{31} \sum_{p=0}^{31} b_{i,j} \cdot b_{i,p} \cdot 2^{j+p}}{2^n}$

让我萌来交换求和顺序：

$\displaystyle E=\sum_{j=0}^{31} \sum_{p=0}^{31} 2^{j+p}\frac{\sum_{i=1}^{2^n}b_{i,j}b_{i,p}}{2^n}$

接下来就是统计某一个异或出来的数的第$j$位和第$p$位同时是$1$的方案数啦。也就是说，要选取一些数，使得它们第$j$位和第$p$位上$1$的个数都是奇数。

$j=p$的情况

这和$k=1$是几乎一样的，就变成了

$\displaystyle 原式=\sum_{j=0}^{31}2^{2j} \frac{\sum_{i=1}^{2^n}[b_{i,j}=1]}{2^n}=\sum_{j=0}^{31}2^{2j} \frac{\sum_{i=1}^{2^n}b_{i,j}}{2^n}=\sum_{j=0}^{31} 2^{2j}\left( \sum_{q=1}^{\lfloor \frac{a+1}{2} \rfloor} \mathrm{C}_a^{2q-1} \right) 2^{n-a} \frac{1}{2^n}=\sum_{j=0}^{31}\left(2^{2j-1} \quad |第j位上有1\right)$

$j \not =p$的情况

$\displaystyle 原式=\sum_{j=0}^{31} \sum_{p \not =j} 2^{j+p} \frac{\sum_{i=1}^{2^n}[b_{i,j}=1 且 b_{i,p}=1]}{2^n}=2\sum_{j=0}^{31} \sum_{p>j}2^{j+p} \frac{\sum_{i=1}^{2^n}[b_{i,j}=1 且 b_{i,p}=1]}{2^n}=\sum_{j=0}^{31} \sum_{p>j}2^{j+p} \frac{\sum_{i=1}^{2^n}[b_{i,j}=1 且 b_{i,p}=1]}{2^{n-1}}$

两个位置$(b_{i,j},b_{i,p})$一共有四种情况：$(1,1)$，$(1,0)$，$(0,1)$，$(0,0)$。设这两位上有$a$个$(1,1)$，$b$个$(1,0)$，$c$个$(0,1)$，$n-a-b-c$个$(0,0)$，那么我萌要从中选取一些，使得均有奇数个$1$。因此不妨设取$x$个$(1,1)$，$y$个$(1,0)$，$z$个$(0,1)$，$(0,0)$随便取，那么要有$x+y=奇数，x+z=奇数$。分$x$的奇偶讨论，可以很快地得到：

$\displaystyle \mathrm{C}_a^奇\mathrm{C}_b^偶\mathrm{C}_c^偶2^{n-a-b-c}=2^{n-3}$

$\displaystyle \mathrm{C}_a^偶\mathrm{C}_b^奇\mathrm{C}_c^奇2^{n-a-b-c}=2^{n-3}$

注意，这是在$a,b,c>0$时成立的，如果其中有$0$，那么有的数就被强制选了偶，中间组合数求和的结果也会不一样。细节参考程序。

所以直接这样求和即可。

时间复杂度$\mathcal{O}(n \log_2^2n)$。

$k \geqslant 3$

这个时候可以高斯消元啦。消完了直接暴力枚举异或方案。但是要注意到，中间过程求和是可能爆long long的，要自己手写小高精。

代码（C++）

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int L = 2000005, N = 100005;
char buf[L], *p = buf;
template <typename T> void rd(T &t) {
    t = 0;
    while (*p < 48 || *p > 57) ++p;
    do {(t *= 10) += *p - 48; ++p;} while (*p > 47 && *p < 58);
}
int n, k;
ull a[N];
void s1() {
    ull ans = 0;
    for (int i = 1; i <= n; ++i) ans |= a[i];
    cout << ans / 2; if (ans & 1) cout << ".5"; cout << endl;
}
void s2() {
    int m = 0, i, j, k, x, y, z, p, q;
    ull ans = 0;
    bool frac = false;
    for (i = 1; i <= n; ++i) m |= a[i];
    for (j = 1; j < 32; ++j)
        if (m & (1ULL << j)) ans += 1ULL << (2 * j - 1);
    if (m & 1) frac = true;
    for (j = 0; j < 31; ++j)
        for (k = j + 1; k < 32; ++k) {
            x = y = z = 0;
            for (i = 1; i <= n; ++i) {
                p = a[i] & (1ULL << j); q = a[i] & (1ULL << k);
                if (p) if (q) ++x; else ++y;
                else if (q) ++z;
            }
            if ((x && y && z) || (x && y && !z) || (x && !y && z) || (!x && y && z)) ans += 1ULL << j + k - 1;
            if (x && !y && !z) ans += 1ULL << j + k;
        }
    cout << ans; if (frac) cout << ".5"; cout << endl;
}
void s345() {
    int i, l, j, S, tmp;
    ull s, p, q, z1 = 0, z2 = 0, b;
    for (i = 0, l = 1; i < 21; ++i) {
        for (j = l; j <= n; ++j) if (a[j] & (1 << i)) break;
        if (j > n) continue;
        swap(a[l], a[j]);
        for (j = 1; j <= n; ++j)
            if (j != l && (a[j] & (1 << i))) a[j] ^= a[l];
        ++l;
    }
    --l;
    for (S = 1; S < (1 << l); ++S) {
        tmp = p = 0; q = 1;
        for (i = 1; i <= l; ++i)
            if (S & (1 << i - 1)) tmp ^= a[i];
        for (i = 0; i < k; ++i) {p *= tmp; q *= tmp; p += q >> l; q &= ((1 << l) - 1);}
        z1 += p; z2 += q;
    }
    z1 += z2 >> l; z2 &= (1 << l) - 1;
    cout << z1; if (z2) cout << ".5"; cout << endl;
}
int main() {
    fread(buf, 1, L, stdin);
    int i;
    rd(n); rd(k);
    for (i = 1; i <= n; ++i) rd(a[i]);
    if (k == 1) s1();
    else if (k == 2) s2();
    else s345();
    return 0;
}

完结撒花！

毕姥爷太强啦！