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的,自然没什么差别,但是用哪种就是仁者见仁智者见智了。

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

【代码】

+

时间: 12-24

BZOJ 2844 albus就是要第一个出场 ——高斯消元 线性基的相关文章

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

题目大意:给出一个长度为n的正整数数列A.每次选出A的一个子集进行抑或(空集抑或值为0),这样就得到一个长度为2^n的数列B.将B中元素升序排序.给出一个数字m,求m的B中出现的最小位置. 思路:线性基的性质:假设n个数可以消出k个线性基,那么显然会有2^k个不同的亦或和,n个数相互排列显然会有2^n个.神奇的事情就在于每种亦或和居然是一样多的,也就是都是2^(n - k)个.有了这个解决这个题就简单了,做一下高斯消元来求出线性基.正常的求法不行,因为要保证消元的时候一个位置上只能有一个1. C

BZOJ 2844 albus就是要第一个出场 高斯消元

题目大意:给定一个n个数的集合S和一个数x,求x在S的2^n个子集从大到小的异或和序列中最早出现的位置 有学长真好不用自己打题目大意了233 首先我们求出线性基 我们会得到一些从大到小排列的数和一堆0 记录0的个数 不考虑0,看前面的数,由于线性基的性质,我们直接贪心从大到小枚举 若当前异或和异或这个值小于Q则取这个数 (注意^不要写成+或者| 本蒟蒻已经因为这个WA了两道题了 然后我们通过每个数取不取可以得到一个01序列 这个序列就是通过异或可以得到的小于Q的数的数量的二进制 比如线性基是8

【BZOJ2844】albus就是要第一个出场 高斯消元求线性基

[BZOJ2844]albus就是要第一个出场 Description 已知一个长度为n的正整数序列A(下标从1开始), 令 S = { x | 1 <= x <= n }, S 的幂集2^S定义为S 所有子集构成的集合.定义映射 f : 2^S -> Zf(空集) = 0f(T) = XOR A[t] , 对于一切t属于T现在albus把2^S中每个集合的f值计算出来, 从小到大排成一行, 记为序列B(下标从1开始). 给定一个数, 那么这个数在序列B中第1次出现时的下标是多少呢? I

BZOJ 2844: albus就是要第一个出场

2844: albus就是要第一个出场 Time Limit: 6 Sec  Memory Limit: 128 MBSubmit: 1134  Solved: 481[Submit][Status][Discuss] Description 已知一个长度为n的正整数序列A(下标从1开始), 令 S = { x | 1 <= x <= n }, S 的幂集2^S定义为S 所有子 集构成的集合.定义映射 f : 2^S -> Zf(空集) = 0f(T) = XOR A[t] , 对于一切

bzoj 2844: albus就是要第一个出场 线性基

首先线性基是什么呢.我们考虑我们有n个数.子集数量为2^n个.我们将每个子集内的数全部异或起来.得到一个值.但是我们考虑这些值内会可能存在重复的,太多了.不便于运算.所以我们考虑,能不能除去重复的. 我们假定n个数都是<10^9.我们考虑使用一个30*30的矩阵.其中其中第一行,存一个最高位1位于数字第1位的数.第二行存一个最高位1位于数字2位的数.以此类推.这样子我们可以得到一个30*30的的矩阵.这个矩阵未必每一行都填满.我们可以考虑,加入一个元素,发现他对应的行已经被填满了.我们将这个数和

【BZOJ 4171】 4171: Rhl的游戏 (高斯消元)

4171: Rhl的游戏 Time Limit: 20 Sec  Memory Limit: 128 MBSubmit: 74  Solved: 33[Submit][Status][Discuss] Description RHL最近迷上一个小游戏:Flip it.游戏的规则很简单,在一个N*M的格子上,有一些格子是黑色,有一些是白色 .每选择一个格子按一次,格子以及周围边相邻的格子都会翻转颜色(边相邻指至少与该格子有一条公共边的格子 ),黑变白,白变黑.RHL希望把所有格子都变成白色的.不幸

bzoj 1013 [JSOI2008]球形空间产生器sphere(高斯消元)

1013: [JSOI2008]球形空间产生器sphere Time Limit: 1 Sec  Memory Limit: 162 MBSubmit: 3584  Solved: 1863[Submit][Status][Discuss] Description 有一个球形空间产生器能够在n维空间中产生一个坚硬的球体.现在,你被困在了这个n维球体中,你只知道球面上n+1个点的坐标,你需要以最快的速度确定这个n维球体的球心坐标,以便于摧毁这个球形空间产生器. Input 第一行是一个整数,n.接

BZOJ 1013 [JSOI2008]球形空间产生器sphere 【高斯消元】

Description 有一个球形空间产生器能够在n维空间中产生一个坚硬的球体.现在,你被困在了这个n维球体中,你只知道球面上n+1个点的坐标,你需要以最快的速度确定这个n维球体的球心坐标,以便于摧毁这个球形空间产生器. HINT 1<=n<=10 提示:给出两个定义:1. 球心:到球面上任意一点距离都相等的点.2. 距离:设两个n为空间上的点A, B的坐标为(a1, a2, …, an), (b1, b2, …, bn),则AB的距离定义为:dist = sqrt( (a1-b1)^2 +

BZOJ 3601 一个人的数论 莫比乌斯反演+高斯消元

题目大意:求Σ[i|n]i^d 围观题解:http://www.cnblogs.com/jianglangcaijin/p/4033399.html 果然我还是太蒻了- - 此外Σ[1<=i<=n]i^m的零次项注定为0- - 所以常数项不用消了- - #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 110 #defin