SRM 621 div2 1000

给一组数, 求异或运算下组成数组的基的元素个数, 1<=n<=50
题解中提到了线性无关, 空间的基QAQ

观察1
..:
所谓``异或运算下''就是所有元素由基中元素的异或产生
注意异或属于模2运算, 即对某数异或的结果只有异或奇数次和异或偶数次两种

举例
..:
若基是{1, 2}, 那么可产生所有元素是{1, 2, 3}
..:
若给出的是{1, 2, 3, 4, 5}
转为01表示
0001
0010
0011
0100
0101
立即使用线性代数中办法
设i从第一行开始, 对i行逐位扫描, i行后的每一行如果同位为1, 就异或, 1<=i<n
..:
其实就是化简矩阵求出线性无关向量的办法, 只不过这里是异或且只异或一次
..:
逐位扫描可以用__builtin_ffs, 也可以用__builtin__clz, 扫描方向不同罢了~~

写出代码
..:

#include <bits/stdc++.h>
using namespace std;

int n, r;
inline void dodo(vector<int>& c, int x) {
    for (int i=x+1; i<n; i++) if (c[i]&(1<<__builtin_ffs(c[x])-1))
        c[i]^=c[x];
}
class MixingColors {
public:
    int minColors(vector <int> c) {
        n=c.size();
        for (int i=0; i<n; i++) if (c[i]) dodo(c, i);
        for (int i=0; i<n; i++) if (c[i]) r++;
        return r;
    }
};