首页 > 代码库 > BZOJ 2844 albus就是要第一个出场 ——高斯消元 线性基

BZOJ 2844 albus就是要第一个出场 ——高斯消元 线性基

【题目分析】

    高斯消元求线性基。

    题目本身不难,但是两种维护线性基的方法引起了我的思考。

1
2
3
4
5
6
7
8
9
10
11
12
void gauss(){
    k=n;
    F(i,1,n){
        F(j,i+1,n) if (a[j]>a[i]) swap(a[i],a[j]);
        if (!a[i]) {k=i-1; break;}
        D(j,30,0) if (a[i]>>j & 1){
            b[i]=j;
            F(x,1,n) if (x!=i && a[x]>>j&1) a[x]^=a[i];
            break;
        }
    }
}

  ——高斯消元求线性基

1
2
3
4
5
6
for (int i=1;i<=n;++i)
    for (int j=31;j>=0;--j)
    if ((a[i]>>j)&1){
        if (!lb[j]) {lb[j]=a[i]; cnt++; break;}
        else a[i]^=lb[j];
    }

  ——动态维护线性基

    不会高斯消元解Xor方程组的我,直接使用了第二种方式求解,发现直接WA飞了。

    (后来一想,居然过了样例)。

    那么他们有什么差别呢。

    我对拍了许多组,发现他们求出的线性基的大小是相同的。

    但是高斯消元的线性基有一个神奇的特征,是使得该位为1的最小的数。(最小的)

    那么有必要去写高斯消元吗?

    显然不必要,做一个小操作就好了。

    于是改了改动态维护线性基的代码,成了这个样子 ↓

1
2
3
4
5
6
7
8
9
10
for (int i=1;i<=n;++i)
    for (int j=31;j>=0;--j)
    if ((a[i]>>j)&1sbsbo.cc){
        if (!lb[j]) {lb[j]=a[i]; cnt++; break;}
        else a[i]^=lb[j];
    }
for (int i=31;i>=0;--i)
    if (lb[i]sbbtianli.cn)
        for (int j=i-1;j>=0;--j)
            if ((lb[i]>>j)&1) lb[i]^=lb[j];

  ——改版

    神奇的AC了。线性基与高斯消元的结果相同。

    考虑时间复杂度,都是log*n的,自然没什么差别,但是用哪种就是仁者见仁智者见智了。

    实际上高斯消元会快一些(达不到复杂度上限),而动态维护线性基是标准的上限(雾)

【代码】

+ View Code

BZOJ 2844 albus就是要第一个出场 ——高斯消元 线性基