题解：P11713 [清华集训 2014] 玛里苟斯

· · 题解

线性代数好题。

首先，第一步观察就是你可以直接将 S 替换为 S 的线性基。虽然不改变能异或出来的数，但是会不会影响方案数导致期望变了？其实是不会的，设线性基大小为 \rm dim(V)，因为线性基内部的元素可以支配最后的异或值，所以任何一个能被表示出来的数，其在线性基外面每个数都可以随便选或者不选，方案数为 2^{n-\rm dim(V)} 都是相同的，线性基内部每个数是否被选择就就唯一确定了，方案数为 1。故每个数方案数相同，直接换成线性基之后还是方案数相同。

于是我们要求的就是线性基中所有能被表示出来的 x，对其 x^k 之后求平均值。将 x 进行二进制拆分，x=\sum\limits_{i=0}^{\log x}b_i2^i，其中 b_i\in \{0,1\}。(\sum\limits_{i=0}^{\log x}b_i2^i)^k 的组合意义就是从所有二进制位中可重复地选择 k 个二进制位，把他们的大小相乘之后对于所有方案求和。

直接暴力枚举选择哪 k 个的复杂度是 \log^k V，可以接受。问题是我们现在手头上并没有具体的线性基能表示出来的数字的集合，一共有 2^{\rm dim(V)} 种数也不可能全部都枚举出来，这个量非常大。

于是我们先枚举这 k 个二进制位求出乘积之后算有多少种从线性基中选择数的方案使得其可以包含这 k 个二进制位。然后用乘积乘以方案数累加进答案。由于是期望所以最后要乘以 \dfrac{1}{2^{\rm dim(V)}}。

为了包含这 k 个二进制位，我们再次对于这 k 个二进制位（离散化为 [0,k-1]）建立线性基来求方案数。设新的线性基大小为 \dim(V')，那么最后包含这 k 个二进制位的方案数就是 2^{\rm dim(V)-\rm dim(V')}，除以 \rm dim(V) 之后，贡献系数就是 2^{-\rm dim(V')}。最后乘上 k 个二进制位的乘积即可。

还有一个问题就是精度不会爆掉吗？可以发现唯一出现小数的地方是 2^{-\rm dim(V')} 这个地方，假设选择的 k 个二进制位中不同的位子的个数为 m。那么 {\rm dim}(V')\le m，一个进制位 i 会贡献 2^i，所以除非 i=0，否则绝大部分情况都是会至少抵消甚至贡献更多的 2。只有当 m=1，i=0 或者 m=2,i\in \{0,1\} 的时候才会出现 \dfrac{1}{2} 的系数，这个好处理，我们先给答案乘以 2，最后再判断奇偶性看看是否需要加上 0.5 即可。

时间复杂度为 O(k\log^{k+1} V)。

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int maxn=70;
struct BASE{
    int lim; ull c[maxn];
    void init(int z){ lim=z; for(int i=0;i<=z;i++) c[i]=0; }
    bool insert(ull v){
        for(int i=lim;i>=0;i--){
            if(!(v&(1ull<<i))) continue;
            if(!c[i]){ c[i]=v; return 1; }
            v^=c[i];
        }
        return 0;
    }
    bool chk(ull v){
        for(int i=lim;i>=0;i--)
            if(v&(1ll<<i)) v^=c[i];
        return (!v);
    }
}b,b2;
int n,m,k,d[maxn],e[maxn]; ull ans=0;
void dfs(int x){
    if(x==k+1){
        int res=1; b2.init(k-1);
        for(int i=1;i<=k;i++) res+=e[i];
        for(int i=0;i<=m;i++){
            if(!b.c[i]) continue;
            int z=d[i],x=0;
            for(int j=1;j<=k;j++)
                if(b.c[i]&(1ull<<e[j])) x|=(1<<j-1);
            if(b2.insert(x)) res--;
        }
        if(b2.chk((1<<k)-1)) ans+=(1ull<<res); return ;
    }
    for(int i=0;i<=m;i++) e[x]=i,dfs(x+1);
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>n>>k; b.init(63);
    for(int i=1;i<=n;i++){
        ull v; cin>>v;
        b.insert(v);
    }
    m=63; while(!b.c[m]) m--; dfs(1);
    if(ans%2==0) cout<<ans/2;
    else cout<<ans/2<<".5";
    return 0;
}