线性基学习笔记

Published on 2016-12-12

先说明一点,aia_i 表示一个标量,而加粗的 ai\mathbf{a}_i 表示一个向量,以便于区分。

概述

基(basis)是线性代数中的一个概念,它是描述、刻画向量空间的基本工具。而在现行的 OI 题目中,通常在利用基在异或空间中的一些特殊性质来解决题目,而这一类题目所涉及的知识点被称作「线性基」。

预备知识

这里有一些线性代数的基本知识,以便更好的理解基的概念。

向量空间(vector space)

向量空间 - 维基百科

定义 (F,V,+,)(F, V, +, \cdot)向量空间(vector space),其中 FF 为域,VV 为集合,VV 中元素称为向量,++ 为向量加法,\cdot 为标量乘法,且运算满足 8 条公理(见维基百科)。

线性无关(linearly independent)

线性无关 - 维基百科

对于向量空间中 VVnn 个元素的向量组 (v1,,vn)(\mathbf{v}_1, \ldots, \mathbf{v}_n),若存在不全为 00 的数 aiFa_i \in F,满足

a1v1+a2v2++anvn=0 a_{1}\mathbf {v} _{1}+a_{2}\mathbf {v} _{2}+\ldots +a_{n}\mathbf {v} _{n} = 0

则称这 nn 个向量线性相关(linearly dependent),否则称为线性无关(linearly independent)

线性组合(linear combination)

线性组合 - 维基百科

对于向量空间中 VVnn 个元素的向量组 (v1,,vn)(\mathbf{v}_1, \ldots, \mathbf{v}_n),其线性组合(linear combination)是如下形式的向量

a1v1+a2v2++anvn a_{1}\mathbf{v}_{1} + a_{2}\mathbf {v} _{2}+\ldots +a_{n}\mathbf {v} _{n}

其中 a1,,anFa_1, \ldots, a_n \in F

一组向量线性无关 \Leftrightarrow 没有向量可用有限个其他向量的线性组合所表示

张成(span)

对于向量空间中 VVnn 个元素的向量组 (v1,,vn)(\mathbf{v}_1, \ldots, \mathbf{v}_n),其所有线性组合所构成的集合称为 (v1,,vn)(\mathbf{v}_1, \ldots, \mathbf{v}_n)张成(span),记为 span(v1,,vn)\mathrm{span}(\mathbf{v}_1, \ldots, \mathbf{v}_n)

基(basis)

基(线性代数)

若向量空间 VV 中向量组 B\mathfrak {B} 既是线性无关的又可以张成 VV,则称其为 VV基(basis)

B\mathfrak {B} 中的元素称为基向量。如果基中元素个数有限,就称向量空间为有限维向量空间,将元素的个数称作向量空间的维数。

性质

B\mathfrak {B} 是向量空间 VV 的基。则 B\mathfrak {B} 具有以下性质:

  1. VVB\mathfrak {B} 的极小生成集,就是说只有 B\mathfrak {B} 能张成 VV,而它的任何真子集都不张成全部的向量空间。
  2. B\mathfrak {B}VV 中线性无关向量的极大集合,就是说 B\mathfrak {B}VV 中是线性无关集合,而且 VV 中没有其他线性无关集合包含它作为真子集。
  3. VV 中所有的向量都可以按唯一的方式表达为 B\mathfrak {B} 中向量的线性组合。

第三点尤其重要,感性的理解,基就是向量空间中的一个子集,它可以通过唯一的线性组合,来张成向量空间中所有的向量,这样就可以大大的缩小我们向量空间的大小。

线性相关性引理(Linear Dependent Lemma)

如果 (v1,,vn)(\mathbf{v}_1, \ldots, \mathbf{v}_n)VV 中是线性相关的,并且 v10\mathbf{v}_1 \neq 0,则有至少一个 j{2,,m}j \in \{2, \ldots, m\} 使得下列成立:

  1. vjspan(v1,,vj1)\mathbf{v}_j \in \mathrm{span}(\mathbf{v}_1, \ldots, \mathbf{v}_{j - 1})
  2. 如果从 (v1,,vn)(\mathbf{v}_1, \ldots, \mathbf{v}_n) 去掉第 jj 项,则剩余向量组的张成仍然等于 span(v1,,vn)\mathrm{span}(\mathbf{v}_1, \ldots, \mathbf{v_n})

证明:(v1,,vn)(\mathbf{v}_1, \ldots, \mathbf{v}_n)VV 中是线性相关的,并且 v10\mathbf{v}_1 \neq \mathbf{0},则有不全为 00a1,,anFa_1, \ldots, a_n \in F,使得

a1v1++amvm=0 a_1\mathbf{v}_1 + \ldots + a_m\mathbf{v}_m = \mathbf{0}

a2,a3,,ana_2, a_3, \ldots, a_n 不会全为 00(因为 v10\mathbf{v}_1 \neq \mathbf{0})。设 jj{2,,m}\{2, \ldots, m\} 中使得 aj0a_j \neq 0 的最大者,那么

vj=a1ajv1aj1ajvj1 \mathbf{v}_j = -\frac {a_1} {a_j}\mathbf{v}_1 - \ldots - \frac {a_{j - 1}} {a_j}\mathbf{v}_{j - 1}

这就有 (1)(1) 成立。

为了证明 (2)(2),设 uspan(v1,,vn)\mathbf{u} \in \mathrm{span}(\mathbf{v}_1, \ldots, \mathbf{v}_n),则存在 c1,,cnFc_1, \ldots, c_n \in F,使得

u=c1v1++cnvn \mathbf{u} = c_1\mathbf{v}_1 + \ldots + c_n\mathbf{v}_n

在上面的等式中,可以用之前的等式右边来代替 vj\mathbf{v}_j。这样 u\mathbf{u} 包含于从 (v0,,vn)(\mathbf{v}_0, \ldots, \mathbf{v}_n) 去掉第 jj 项的张成,因而 (2)(2) 成立。

OI 中的线性基

异或运算下的基

求法

对于数 a0,a1,,ana_0, a_1, \ldots, a_n,将 aia_i 的二进制表示 (bmb0)2(b_{m}\ldots b_0)_2 看作一个向量 ai=(bm,,b0)\mathbf{a}_i = (b_m, \ldots, b_0),为了叙述上的方便,下文称向量 ai\mathbf{a}_i 的第 jj 位为 bjb_j

向量组 a1,,an\mathbf{a}_1, \ldots, \mathbf{a}_n 可以张成一个向量集合 span(a1,,an)\mathrm{span}(\mathbf{a}_1, \ldots, \mathbf{a}_n),加上我们的异或运算和乘法运算(显然满足 8 条公理),即可形成一个向量空间 V=({0,1},span(a1,,an),,)V = (\{0, 1\}, \mathrm{span}(\mathbf{a}_1, \ldots, \mathbf{a}_n), \oplus, \cdot)

我们考虑求出向量空间 VV 的一个基 B\mathfrak{B},从 B=(a1,,an)\mathfrak{B} = (\mathbf{a}_1, \ldots, \mathbf{a}_n) 开始。

第 1 步:如果 a1=0\mathbf{a}_1 = \mathbf{0},则从 B\mathfrak{B} 中去掉 a1\mathbf{a_1},否则保持 B\mathfrak{B} 不变。
第 j 步:ajspan(a1,,aj1)\mathbf{a}_j \in \mathrm{span}(\mathbf{a}_1, \ldots, \mathbf{a}_{j - 1}),则从 B\mathfrak{B} 中去掉 aj\mathbf{a}_j,否则保持 B\mathfrak{B} 不变。

经过 nn 步后终止程序,得到一个向量组 B\mathfrak{B}。由于每一次去掉的向包含于前面诸向量的张成,到最后这个组 B\mathfrak{B} 仍然可以张成 VV。而且这一程序确保了 B\mathfrak{B} 中的任何向量都不包含与它前面诸向量的张成,根据线性相关性引理可知 B\mathfrak{B} 是线性无关的。于是 B\mathfrak{B}VV 的一个基。

利用高斯消元来判断向量能否被前面的向量张成,就可以写出下面的程序:

void cal() {
    for (int i = 0; i < n; ++i)
        for (int j = MAX_BASE; j >= 0; --j)
            if (a[i] >> j & 1) {
                if (b[j]) a[i] ^= b[j];
                else {
                    b[j] = a[i];
                    for (int k = j - 1; k >= 0; --k) if (b[k] && (b[j] >> k & 1)) b[j] ^= b[k];
                    for (int k = j + 1; k <= MAX_BASE; ++k) if (b[k] >> j & 1) b[k] ^= b[j];
                    break;
                }
}

这个程序实现的非常精妙,我们每次维护一个对角矩阵。执行到第 ii 步的时候,我们从高到低考虑数 aia_i11 的二进制位 jj,如果 jj 这一行的对角线已经为 11 了,那么我们不能加入,同时为了保持上三角性质,需要将第 jj 行的行向量异或到 ai\mathbf{a}_i;如果 jj 这一行的对角线为 00,那么我们就可以将 ai\mathbf{a}_i 添加到这一行,同时为了维护一个对角矩阵,要先用下面的行消自己,再用自己消上面的行。

如果一个向量 ai\mathbf{a}_i 能被 a1,,ai1\mathbf{a}_1, \ldots, \mathbf{a}_{i - 1} 张成,它不应添加进 B\mathfrak{B},在高斯消元的过程中它必然是已经存在的行向量的线性组合,所以这个方程实际上是多余的,它最后一定会被异或为一个 0\mathbf{0}。反之如果向量 ai\mathbf{a}_i 不能被 a1,,ai1\mathbf{a}_1, \ldots, \mathbf{a}_{i - 1} 张成,那么它一定能找到某一个行添加进去。

我们来模拟下这个过程,n=5,a={7,1,4,3,5}n = 5, a = \{7, 1, 4, 3, 5\}。一开始矩阵是这样的:

[000000000] \begin{bmatrix} 0 & 0 & 0\\ 0 & 0 & 0\\ 0 & 0 & 0 \end{bmatrix}

加入 7=(111)27 = (111)_2,矩阵变为:

[111000000] \begin{bmatrix} 1 & 1 & 1\\ 0 & 0 & 0\\ 0 & 0 & 0 \end{bmatrix}

加入 1=(001)21 = (001)_2,添加到最后一行,同时为了维护对角矩阵,消去第一行的最低位,矩阵变为:

[110000001] \begin{bmatrix} 1 & 1 & 0\\ 0 & 0 & 0\\ 0 & 0 & 1 \end{bmatrix}

加入 4=(100)24 = (100)_2,由于第一行已经有数了,它被异或为 (010)2(010)_2,加入第二行,同时为了维护对角矩阵,消去第一行的第二位,矩阵变为:

[100010001] \begin{bmatrix} 1 & 0 & 0\\ 0 & 1 & 0\\ 0 & 0 & 1 \end{bmatrix}

剩下的数都加不上了。

这样所有被选上的 ai\mathbf{a}_i 构成一个向量空间 VV 的一个基 B\mathfrak{B}。同时我们知道高斯消元最后得到的矩阵 bbB\mathfrak{B} 中的向量构成的矩阵进行若干初等行变换得到的矩阵,而任意初等行变换不会影响向量之间的线性无关性,且任意初等行变换过后,这些向量仍然能够张成原有的向量空间(不难证明)。所以,所有非 0\mathbf{0}bi\mathbf{b}_i 仍然构成向量空间 VV 的一个基。

大家所称的「线性基」一般都指这个方式得到的基,因为这个基具有一个独特的性质,可以应用到 OI 题目中。所以我们一般谈论的线性基,特指高斯消元解出的对角矩阵的非零行构成的向量组。

性质

对于最后得到的矩阵,如果第 ii 的主对角线上为 11,此时我们称第 ii 位存在于线性基中。对于存在于线性基的二进制位,有一个重要的性质:

对于任意存在于线性基的二进制位 ii,至多只有一个 bj\mathbf{b}_j 满足第 ii 位为 11

证明:高斯消元的过程中,我们维护了一个对角矩阵,如果二进制位 ii 存在于一个向量 bj\mathbf{b}_j 上,那么 bj\mathbf{b}_j 它一定消去了别的向量第 ii 位上的 11,故二进制位 ii 只存在于 bj\mathbf{b}_j 上。

自然,对于不在线性基中的二进制位 ii,那么第 ii 行主对角线下方全为 00,而主对角线上方就可能有若干个 11

注意

上述高斯消元过程是消成了一个对角矩阵,如果消成上三角矩阵,虽然不具备这个性质,但是仍然能知道那些二进制位 ii 存在于线性基中,有时为了代码的简便,只消成上三角矩阵。下文不做区分,请自行判断。

下面例题中用 VV 代指将题目中所有数的张成与异或运算和乘法运算构成的向量空间。

例一(SGU 275)

给定 n(1n100000)n(1\le n\le 100000) 个数 a1,a2,,ana_1, a_2, \ldots, a_n,请问这些数能够组成的最大异或和是什么?

分析

我们求出向量空间 VV 的一组线性基。则答案就是将线性基中所有向量异或起来得到的向量所对应的数。

考虑用归纳法证明。因为最高的二进制位只存在于最大的基向量上(用向量所代表的二进制数来比大小),所以最大的基向量肯定要选。接着假设前 ii 大的都需要选,考虑第 i+1i + 1 大的基向量选不选。显然 i+1i + 1 大的基向量能对异或和贡献它的最高的二进制位 jj,因为二进制位 jj 在之前的异或和中必然为 00(根据性质,jj 只存在于第 i+1i + 1 大的基向量中)。如果不选,之后所有数对答案的贡献都只能在小于这个二进制位的地方做贡献,总是比选 i+1i + 1 得到的答案小,所以这个数必须得选。

例二(HDOJ 3949)

给定 n(n10000)n(n \le 10000) 个数 a1,a2,,ana_1, a_2, \ldots, a_n,以及 Q(Q10000)Q(Q\le 10000) 个询问,每次询问这些数(至少一个,不能不选)能够组成的异或和中第 kk 小的数是什么(去掉重复的异或和)。

分析

我们求出向量空间 VV 的一组线性基 B\mathfrak{B}。因为向量空间中的任意向量 u\mathbf{u} 均可以被表示称 B\mathfrak{B} 中向量的唯一线性组合,所以 B\mathfrak{B} 中的任意非空子集都可以构成一个向量且互不重复。所以这些数能够组成的异或和的个数为 2B12^{\vert \mathfrak{B}\vert} - 1,特别的,如果 B<n\vert\mathfrak{B}\vert < n,则必然存在一个向量组满足线性相关性,这个向量组也就能通过线性组合,异或得到 00,则异或和的个数为 2B2^{\vert \mathfrak{B}\vert}

假设线性基中有 mm 个基向量,从小到大依次为 (v0,,vm1)(\mathbf{v}_0, \ldots, \mathbf{v}_{m - 1}),则第 k=(bxb0)2k = (b_x\ldots b_0)_2 小的数就是:

0ixbivi \oplus_{0\le i\le x}b_i \cdot v_i

不难用二进制的思想证明。

代码

//  Created by Sengxian on 2016/12/5.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  HDOJ 3949 线性基
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
inline ll readLL() {
    static ll n;
    static int ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = n * 10 + ch - '0', ch = getchar();
    return n;
}

const int MAX_N = 100000 + 3, MAX_BASE = 60;
int n, zero = false;
ll a[MAX_N], b[MAX_BASE + 3];
vector<ll> mmap;

void prepare() {
    int cnt = 0;
    memset(b, 0, sizeof b);
    for (int i = 0; i < n; ++i)
        for (int j = MAX_BASE; j >= 0; --j)
            if (a[i] >> j & 1) {
                if (b[j]) a[i] ^= b[j];
                else {
                    b[j] = a[i], cnt++;
                    for (int k = j - 1; k >= 0; --k) if (b[k] && ((b[j] >> k) & 1)) b[j] ^= b[k];
                    for (int k = j + 1; k <= MAX_BASE; ++k) if ((b[k] >> j) & 1) b[k] ^= b[j];
                    break;
                }
            }
    zero = cnt != n;

    mmap.clear();
    for (int i = 0; i <= MAX_BASE; ++i)
        if (b[i]) mmap.push_back(b[i]);
}

ll query(ll k) {
    if (zero) k--;
    if (k >= (1LL << (int)mmap.size())) return -1;
    ll ans = 0;
    for (int i = 0; i < (int)mmap.size(); ++i) if ((k >> i) & 1)
        ans ^= mmap[i];
    return ans;
}

int main() {
#ifdef DEBUG
    freopen("test.in", "r", stdin);
#endif
    int caseNum = readLL();
    for (int t = 1; t <= caseNum; ++t) {
        n = readLL();
        for (int i = 0; i < n; ++i) a[i] = readLL();

        prepare();

        printf("Case #%d:\n", t);
        int q = readLL();
        for (int i = 0; i < q; ++i) printf("%lld\n", query(readLL()));
    }
    return 0;
}

例三(BZOJ 2115)

给定一个 n(n50000)n(n\le 50000) 个点 m(m10000)m(m\le 10000) 条边的无向图,每条边上有一个权值。请你求一条从 11nn 的路径,使得路径上的边的异或和最大。

分析

任意一条 11nn 的路径的异或和,都可以由任意一条 11nn 路径的异或和与图中的一些环的异或和来组合得到。

为什么?假如我们已经有一条 11nn 的路径,考虑在出发之前,先走到图中任意一个环上面,走一遍这个环,然后原路返回,这样我们既得到了这个环的异或值(走到环的路径被走过了 2 次,抵消了),也返回了点 11。我们可以对任意的环这样做,从而获得这个环的异或值。有了这个性质,不难验证上述结论是正确的。

现在的解题思路就非常明确了,首先找出所有的环(利用 DFS 树中的返祖边来找环),然后找一条任意的 11nn 的路径,其异或值为 ss。则我们就需要选择若干个环,使得这些这些环上的异或值与 ss 异或起来最大。这就转化为线性基的问题了。

求出所有环的异或值的线性基,由于线性基的良好性质,只需要从大到小考虑选择每个线性基向量能否使得异或值更大即可,容易用贪心证明正确性。

证明:从高到低考虑每个二进制位,设当前的答案为 ss,考虑到第 kk 位,线性基向量中代表二进制位 kk 的向量为 v\mathbf{v}。那么对于第 kk 位,一共有三种情况,我们分别考虑我们的选择原则是不是正确的。

  1. ss 中第 kk 位是 11v\mathbf{v} 中第 kk 位是 11,实际上不能选。根据我们的选择原则,此时异或起来答案一定会变小,不选。正确。
  2. ss 中第 kk 位是 00v\mathbf{v} 中第 kk 位是 11,实际上要选。根据我们的选择原则,此时异或起来答案一定会变大,选。正确。
  3. v\mathbf{v} 中第 kk 位是 00,那么 v\mathbf{v} 必定是零向量,选不选无所谓。正确。

所以在每一种情况中,我们的选择原则都是正确的,所以这个贪心也是正确的。

代码

//  Created by Sengxian on 2016/12/05.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  BZOJ 2115 线性基
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
inline ll readLL() {
    static ll n;
    static int ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = n * 10 + ch - '0', ch = getchar();
    return n;
}

const int MAX_N = 50000 + 3, MAX_M = 100000 + 3, MAX_BASE = 60;
struct edge {
    edge *next, *rev;
    int to;
    ll cost;
    edge(edge *next = NULL, int to = 0, ll cost = 0): next(next), to(to), cost(cost) {}
} pool[MAX_M * 2], *pit = pool, *first[MAX_N];
int n, m, cnt = 0;
ll d[MAX_N], a[MAX_N + MAX_M * 2], b[MAX_BASE + 3];

void dfs(int u, edge *fa) {
    static bool vis[MAX_N];
    vis[u] = true;

    for (edge *e = first[u]; e; e = e->next) if (e->rev != fa) {
        if (!vis[e->to]) {
            d[e->to] = d[u] ^ e->cost;
            dfs(e->to, e);
        } else a[cnt++] = d[u] ^ d[e->to] ^ e->cost;
    }
}

void prepare() {
    for (int i = 0; i < cnt; ++i)
        for (int j = MAX_BASE; j >= 0; --j)
            if (a[i] >> j & 1) {
                if (b[j]) a[i] ^= b[j];
                else {
                    b[j] = a[i];
                    for (int k = j - 1; k >= 0; --k) if (b[k] && (b[j] >> k & 1)) b[j] ^= b[k];
                    for (int k = j + 1; k <= MAX_BASE; ++k) if (b[k] >> j & 1) b[k] ^= b[j];
                    break;
                }
            }
}

int main() {
    n = readLL(), m = readLL();
    for (int i = 0; i < m; ++i) {
        int u = readLL() - 1, v = readLL() - 1;
        ll w = readLL();
        first[u] = new (pit++) edge(first[u], v, w);
        first[v] = new (pit++) edge(first[v], u, w);
        first[u]->rev = first[v], first[v]->rev = first[u];
    }

    dfs(0, NULL);
    prepare();

    ll ans = d[n - 1];
    for (int i = MAX_BASE; i >= 0; --i)
        if (ans < (ans ^ b[i])) ans ^= b[i];

    printf("%lld\n", ans);
    return 0;
}

例四(BZOJ 2844)

给定 n(n10000)n(n \le 10000) 个数 a1,a2,,ana_1, a_2, \ldots, a_n,以及一个数 QQ。将 a1,a2,,ana_1, a_2, \ldots, a_n 的所有子集(可以为空)的异或值从小到大排序得到序列 BB,请问 QQBB 中第一次出现的下标是多少?保证 QQBB 中出现。

分析

首先求出 VV 的线性基 B\mathfrak{B}

如果去除序列 BB 中重复的数,使用线性基,根据 QQ 的二进制位便可以确定 QQ 的排名(使用类似例二的方法)。可是如果不去重,怎么才能知道每个数出现多少次呢?

结论:每个数都出现一样的次数,且这个次数为 2nB2^{n - \vert \mathfrak{B}\vert}
证明:我们考虑在 BB 中出现的任意一个数 xx。所有不在线性基中的数的个数为 nBn - \vert \mathfrak{B}\vert,我们任意选择它的一个子集 SS,对于 SS 中的每个数 vv,有唯一的方式表达为 B\mathfrak {B} 中向量的线性组合。我们对于每个 vv,将这个线性组合中的向量都选上(一个向量选多次不要紧),两个相同的数异或起来得到 00,所以对于每个数 xx,我们都能找到 2nB2^{n - \vert \mathfrak{B}\vert} 种不同的选择方案,使得异或值为 xx。又因为对于每个子集 SS,为了使得最终异或值为 xx,选择线性基中的向量的方案是唯一的,所以上界也是 2nB2^{n - \vert \mathfrak{B}\vert}。这就完成了证明。

这样就只需要一个快速幂就能快速计算答案了。

代码

//  Created by Sengxian on 2016/12/07.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  BZOJ 2844 线性基
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
inline int readInt() {
    static int n, ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = n * 10 + ch - '0', ch = getchar();
    return n;
}

const int MAX_N = 100000 + 3, MAX_BASE = 30, MOD = 10086;
int n, a[MAX_N], b[MAX_BASE + 1], Q;

inline int mod_pow(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) (res *= a) %= MOD;
        (a *= a) %= MOD;
        b >>= 1;
    }
    return res;
}

int main() {
    n = readInt();
    for (int i = 0; i < n; ++i) a[i] = readInt();
    Q = readInt();

    int cnt = 0, rnk = 0;
    for (int i = 0; i < n; ++i)
        for (int j = MAX_BASE; j >= 0; --j)
            if (a[i] >> j & 1) {
                if (b[j]) a[i] ^= b[j];
                else {
                    b[j] = a[i];
                    cnt++;
                    break;
                }
            }

    vector<int> vec;
    for (int i = 0; i <= MAX_BASE; ++i) if (b[i]) vec.push_back(i);
    for (int i = 0; i < (int)vec.size(); ++i) if (Q >> vec[i] & 1)
        rnk += 1 << i;

    printf("%d\n", (rnk % MOD * mod_pow(2, n - cnt) % MOD + 1) % MOD);
    return 0;
}

例五

BZOJ 3811

魔法之龙玛里苟斯最近在为加基森拍卖师的削弱而感到伤心,于是他想了一道数学题:SS 是一个可重集合,S={a1,a2,,an}S=\{a_1,a_2,\ldots,a_n\}。等概率随机取 SS 的一个子集 A={ai1,,aim}A=\{a_{i_1},\ldots,a_{i_m}\},计算出 AA 中所有元素的异或值 xx, 求 xk(1k5)x^k(1\le k\le 5) 的期望。

保证答案不超过 2642^{64}

分析

这种题需要求异或值的和,通常的方法是求出线性基之后,考虑每一位的贡献。

我们对每一个 kk 分别考虑。

k=1k = 1 时,由于贡献是线性的,所以我们可以对每一个二进制位分别考虑。我们考虑二进制位 ii,如果在某一个 aja_j 中,存在二进制位 ii11,那么子集的异或和中二进制位 ii11 的概率为 12\frac 1 2。如果不存在这样的 aja_j,概率为 00。证明很容易,因为子集中有奇数个或者偶数个 aja_j 二进制位 ii11 的概率是一样的,而只有奇数个 aja_j 二进制位 ii11 才能满足异或和中二进制位 ii11

k=2k = 2 时,我们求的是期望的平方,即每个异或和的贡献为 (bmbm1b0)2(bmbm1b0)2(b_mb_{m - 1}\ldots b_0)_2\cdot(b_mb_{m - 1}\ldots b_0)_2,写成和式就是

ijbjbi2i+j \sum_{i}\sum_j b_jb_i \cdot 2 ^ {i + j}

我们需要枚举两个二进制位,现在每个数变成了 (0/1,0/1)(0/1,0/1) 二元组,仅当异或后得到 (1,1)(1, 1),才会产生 2i+j2^{i + j} 的贡献。根据 k=1k = 1 的情况不难发现,有 14\frac 1 4 的概率得到 (1,1)(1, 1)。需要特判的是,如果所有数都是 (1,1)(1, 1) 或者 (0,0)(0, 0) 且至少有一个 (1,1)(1, 1),那么概率为 12\frac 1 2。如果所有数都是 (0,0)(0, 0),那么概率为 00

k3k \ge 3 时,由于答案不超过 2642^{64},所以每个数不超过 2222^{22},这些数的线性基不会超过 2222 个,所以我们可以考虑求出线性基,然后暴力枚举线性基的子集即可。

虽然答案不会溢出,但是中间过程是有可能是溢出的,为了防止溢出,在 k1k \neq 1 时,若除数为 2m2^m,那么我们在乘的过程中,将答案记录为 y=y2m2m+ymod2my = \lfloor \frac y {2^m}\rfloor \cdot 2^m + y \bmod 2^m 的形式,这样两个项都不会超过 2642^{64},可以计算了。

现在我们考虑输出小数的问题,当 k=1k = 1 时显然小数位要么是 00 要么是 0.50.5;而 k1k \neq 1 时这个结论仍然成立(虚心求证明),所以特判一下就好了。

代码

//  Created by Sengxian on 2016/12/10.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  BZOJ 3811 线性基
#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ll;
inline ll readLL() {
    static ll n;
    static int ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = n * 10 + ch - '0', ch = getchar();
    return n;
}

const int MAX_N = 100000 + 3, MAX_BASE = 23;
int n, K;
ll a[MAX_N], b[MAX_N];

void solve1() {
    ll res = 0;
    for (int i = 0; i < n; ++i) res |= a[i];
    printf("%llu", res / 2);
    if (res & 1) puts(".5");
    else puts("");
}

void solve2() {
    ll ans = 0, res = 0;
    for (int i = 0; i < 32; ++i)
        for (int j = 0; j < 32; ++j) {
            bool flag = false;
            for (int k = 0; k < n; ++k) if (a[k] >> i & 1) { flag = true; break; }
            if (!flag) continue;
            flag = false;
            for (int k = 0; k < n; ++k) if (a[k] >> j & 1) { flag = true; break; }
            if (!flag) continue;

            flag = false;
            for (int k = 0; k < n; ++k) if ((a[k] >> i & 1) != (a[k] >> j & 1)) { flag = true; break; }

            if (i + j - 1 - flag < 0) res++;
            else {
                if (!flag) ans += 1LL << (i + j - 1); // 1 / 2
                else ans += 1LL << (i + j - 1 - 1); // 1 / 4
            }
        }

    ans += res >> 1, res &= 1;
    printf("%llu", ans);
    if (res) puts(".5");
    else puts("");
}

void solve3() {
    vector<int> vec;
    for (int i = 0; i < n; ++i)
        for (int j = MAX_BASE; j >= 0; --j)
            if (a[i] >> j & 1) {
                if (b[j]) a[i] ^= b[j];
                else {
                    b[j] = a[i];
                    vec.push_back(a[i]);
                    break;
                }
            }

    int all = vec.size();
    ll ans = 0, res = 0;
    for (int i = (1 << all) - 1; i >= 0; --i) {
        int val = 0;
        for (int j = 0; j < (int)vec.size(); ++j) if (i >> j & 1) val ^= vec[j];

        ll a = 0, b = 1;
        for (int j = 0; j < K; ++j) {
            a *= val, b *= val;
            a += b >> all, b &= (1 << all) - 1;
        }

        ans += a, res += b;
        ans += res >> all, res &= (1 << all) - 1;
    }

    printf("%llu", ans);
    if (res) puts(".5");
    else puts("");
}

int main() {
    n = readLL(), K = readLL();
    for (int i = 0; i < n; ++i) a[i] = readLL();

    if (K == 1) solve1();
    else if (K == 2) solve2();
    else solve3();
    return 0;
}

总结

线性基的题型相对比较固定,看到下面的类型基本上都是线性基了:

  1. 最大异或和
  2. kk 大异或和/异或和是第几大
  3. 求所有异或值的和

线性基中的题目中还用到一个技巧:

  • 任意一条 11nn 的路径的异或和,都可以由任意一条 11nn 路径的异或和与图中的一些环的异或和来组合得到。

这便是线性基的全部东西了。