[Medium-Hard] P11713 [清华集训 2014] 玛里苟斯

简要题意

给定一个长度为 $n$ 的序列 $a$。

现随机选取一个子序列，求其异或和的 $k$ 次幂的期望。输出精确值，保证答案 $<2^{63}$。

$1\leq n\leq 10^5,1\leq k\leq 5,a_i\geq 0$。

思路

神仙题。

Part 1

引理：对于可以得到的异或和 $x,y$，异或和为 $x$ 的方案数与异或和为 $y$ 的方案数相等。

证明：取 $a$ 的异或线性基 $V$。则每个数的方案数都是 $2^{n-\dim V}$ 种，因为异或线性基可以看成对一个异或方程组消元得到的，有 $\dim V$ 个自由元，而确定了自由元的取值后，非自由元可以任意选取，有 $2^{n-\dim V}$ 种，而自由元的取值是唯一的。证毕。

于是可以将序列 $a$ 替换为 $a$ 的线性基 $V$，将 $n$ 缩减为 $O(\log a_i)$ 级别。同时答案也就是所有线性基的张成空间的所有元素的 $k$ 次幂平均值。

现在考虑 $a_i$ 的范围，由于保证答案 $\leq 2^{63}$，所以大致上有 $a_i\leq 2^{63/k}$，也就是 $\log a_i\sim \frac{63}{k}$。

Part 2

先来考虑 $k$ 较大的情况，可以暴力枚举线性基的张成空间 $\mathrm{span}(V)$。这需要 $O(2^{\dim V})$ 的时间复杂度。当 $k=3$ 时 $\dim V\sim 21$ 枚举勉强可以接受。注意时间复杂度别做成 $O((\dim V)2^{\dim v})$ 了，这个应该是铁定过不去的。

Part 3

然后考虑 $k=1,k=2$。先来考虑 $k=1$。

不妨将张成空间的所有数二进制分解，考虑所有存在 $1$ 的二进制位。假设这一位上，有 $a$ 个 $1$ 和 $(\dim V)-a$ 个 $0$，那么张成空间在这一位的总贡献为：

$$2^{-a+\dim V}\sum_{i=1}^{a}\binom{a}{i}[i\bmod 2=1]$$

也就是这一位为 $0$ 的数随便选，这一位为 $1$ 的数枚举选择的次数，如果为奇数就有贡献。

有经典的组合恒等式：

$$\sum_{i=1}^{a}\binom{a}{i}[i\bmod 2=1]=2^{a-1}$$

证明只需要根据二项式定理，取下指标为偶数的项与下指标为奇数的项之和 $(1+1)^a=2^a$ 和差 $(1-1)^a=0$ 即可。

所以总贡献是 $2^{\dim V-1}$，只需要枚举每一个可以出现在答案中的位就可以计算出答案（一个巧合：由于 $|\mathrm{span}(V)|=2^{\dim V}$，所以每一位的实际贡献是 $\frac{1}{2}$）。

Part 4

现在来考虑 $k=2$，仍然考虑拆位，记 $P$ 表示合法位集合，则答案是：

$$\frac{1}{2^{\dim V}}\sum_{x\in\mathrm{span}(V)}x^2=\frac{1}{2^{\dim V}}\sum_{x\in P}\sum_{y\in P}2^{x+y} F(x,y)$$

其中 $F(x,y)$ 表示位 $x,y$ 的异或值都为 $1$ 的方案数。

如果 $x,y$ 为 $1$ 的事件是独立的，那么 $F(x,y)\cdot 2^{-\dim V}$ 就应该是 $\frac{1}{4}$。这里的独立实际上就是线性无关，可以通过判断线性基的每一个向量这两位是否相同得到。

否则代表线性相关，只需要一个满足，另一个就会满足，概率 $F(x,y)\cdot 2^{-\dim V}$ 为 $\frac{1}{2}$。

这一部分时间复杂度 $O(\log^2 V)$ 或 $O(\log^3 V)$ 都可以。

代码

#include <bits/stdc++.h>
#define lowbit(x) ((x) & (-(x)))
using namespace std;

using ui64  = unsigned long long;
int n, k, m;
ui64 p[65];

void insert(ui64 x){
    for(int i=63;~i;i--){
        if(!((x >> i) & 1)) continue;
        if(!p[i]) return m++, p[i] = x, void();
        x ^= p[i];
    }
}

ui64 f[(1 << 22) + 5];

__int128 slow_pow(__int128 x, int y){
    switch(y){
    case 3:
        return x * x * x;
    case 4:
        return x * x * x * x;
    case 5:
        return x * x * x * x * x;
    default: __builtin_unreachable();
    }
}

void output(long double ret){ cout << defaultfloat << setprecision(114) << ret << '\n'; }

int buf[65];

void bruteforce(){
    f[0] = 0;
    __int128 ans = 0; int tot = 0;
    for(int i=0;i<=63;i++){
        if(p[i]) buf[tot++] = i;
    }
    for(int i=1;i<(1 << m);i++){
        f[i] = f[i ^ lowbit(i)] ^ p[buf[__lg(lowbit(i))]];
        ans += slow_pow(f[i], k);
    }
    output(1.0L * ans / (1ll << m));
}

void task1(){
    __int128 ans = 0; ui64 tmp = 0;
    for(int i=63;~i;i--) tmp |= p[i];
    for(int i=63;~i;i--){
        if((tmp >> i) & 1) ans += (1ull << i);
    }
    output(0.5L * ans);
}

void task2(){
    __int128 ans = 0; ui64 tmp = 0;
    for(int i=63;~i;i--) tmp |= p[i];
    for(int i=63;~i;i--){
        if(!((tmp >> i) & 1)) continue;
        for(int j=63;~j;j--){
            if(!((tmp >> j) & 1)) continue;
            bool flag = 0;
            for(int k=63;~k;k--) flag |= ((p[k] >> i) & 1) ^ ((p[k] >> j) & 1);
            ans += ((__int128)1 << (i + j + !flag));
        }
    }
    output(0.25L * ans);
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n >> k;
    for(int i=1;i<=n;i++){
        ui64 x; cin >> x;
        insert(x);
    }
    if(k >= 3) bruteforce();
    else if(k == 1) task1();
    else task2();
    return 0;
}

// Written by xiezheyuan

Submission。