线性基
求最大值
暴力从高到低位枚举，如果加入这一位的基答案会更大则加入
求异或值第 小
算出所有线性基后再对于每一个有基的位消元使得没有其他的基这一位为
。最后找出所有这样的基从小到大依次标号为 。问第 小的时候就for一遍 当 第 项为 时就异或上
Q：为什么多了对每一位有基的位消元这一步？
A：因为这样就能保证对于所有 ， 且一旦异或上一个
那么前面的 的一共
种选/不选方式的值都不如这里选了，当前的排名自然就 ，于是这样做就是可行的
注意特判
如果能表示出来则
要减一
求交
首先两个线性基的交也是个线性基，因为比如 且 那么一定有
（即如果两个线性基都能表示出 和
那么它们也一定都能表示出 ）
然后有个引理就是：线性基
是线性基 和 的交当且仅当 和 也可组成一个线性基（即
和 线性无关）
充分性：
即如果 是 和 的交那么 和 线性无关。考虑如果 和 线性相关的话就相当于 和 还有交，与条件矛盾。
必要性：
即如果 和 线性无关则 是 与 的交。考虑一个 如果是 和 的交且不能用 表示，那么即 和 线性相关，又因为 能表示 那么一定是由 那部分表示的 ，并且 也可以表示出 那么 与 都能表示出 ，所以两者不是线性无关与条件矛盾。
然后考虑依次加入 中每个基
且保证加入前 和
线性无关：
- 如果它不能能够被 和
表示则它一定不是
和 的交可以不管。（它属于 ）
- 如果它可以被 和 表示则我们考虑换基。把
用 表示，比如
（这时候有交出现了： 且不能在
中直接加入 因为单凭 无法表示 ）我们把 换成 再加入 中，那么可以发现 能表示的东西不变，且此时 与 又线性无关了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| struct Base{
ll r[N];
inline base(){memset(r,0,sizeof r);}
inline void ins(ll x){
for(int i=N-1;~i;i--)if(x>>i&1){
if(!r[i]){
r[i]=x;
return;
}else x^=r[i];
}
}
inline const int& operator [] (const int &x)const{return r[x];}
inline int& operator [](int x){return r[x];}
inline base operator +(const base &t)const{
base b,c=*this,ans;
for(int i=0;i<N;i++)if(t[i]){
ll v=t[i],vb=t[i],flag=1;
for(int j=N-1;~j;j--)if(v>>j&1){
if(c[j]){
v^=c[j];
vb^=b[j];
}else{
c[j]=v;
b[j]=vb;
flag=0;
break;
}
}
if(flag) ans.ins(vb);
}
return ans;
}
};
|
删除
（保证删除的向量一定之前插入过）
方法一
离线，以时间为下标线段树分治，但要事先知道每个向量的出现时间段
方法二
离线，对每个向量记录他还有多久被删去，插入时如果比这一位的基后删则交换一下，把的这个作为基并继续插入之前这一位的基，删除时看一下剩下的是不是它，是的话直接删就行
这玩意想半天觉得很假发现确实是假的（比如先插一个 和 现在就剩个 和 ，再把 删了应该剩下 实际上剩下 ）怪不得 http://uoj.ac/problem/91
只有两个人的题解写这个还写的基本上一模一样……都 了
实际上挂是那两个人写假了正确性是没问题的比如插入 和 先删除 那么插入 时会把 换成 再插入
。删除时实际上是什么也不做，查询时只考虑删除时间大于当前时间的基向量。
然后有个问题就是这样做的正确性：大概是考虑一个被删除的向量，考虑它出现的最低的
个基向量（也即是它最后插入的位置）比它低的位一定不含它（因为已经在这里插入了），比它高的位中
- 不包含它的，删不删除它 不影响
- 包含他，意味着之前存在某个时间当前这一位 的被删除时间晚于包含它的那一位
包含的某个向量，那之后被删除的这一位跑下来肯定是因为有比其更晚被删除的加入，那么
被换后往下走时一定会经过 且被删除时间晚于 那么就应该是换成 往下走，这与 最终位置比 位置高矛盾，所以得到不存在比当前这一位高的含有这个被删除的向量
（只是当前这一位基可能是由以前的向量和这一个要被删除的向量构成，但还是只有它这一位基含有这个向量，只删除这一个基就行）
例题：UOJ91
Description
我有一个数列 每个
都是小于 的非负整数。
现在请您实现三种操作，格式说明如下：
：对于所有 ，将 修改为 。其中 是一个小于 的非负整数。
：对于所有 ，将 修改为 。其中 是一个小于 的非负整数。 33：从
中选出若干个数，使得选出的数异或和最大。请输出这个最大值。 这里 表示按位异或运算， 的异或和是指 。
Constraints
Solution
首先原序列差分后的线性基和原序列的线性基等价
那么每次操作就只有修改两个位置或者删除一段区间的向量
把修改看成删除再插入，即把上一个当前位置的向量的出现时间右端点改成当前
，把插入新的值的出现时间设为
离线后按照上面的做即可，复杂度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
| #include<bits/stdc++.h>
#define FIO "uoj91"
#define ll long long
using namespace std;
const int N=2e3+5,M=N<<2;
#define bs bitset<N>
int n,m,q;
bs a[N],b[N];
char s[N];
inline bs rd(){
bs a;
scanf("%s",s);
reverse(s,s+m);
for(int i=0;i<m;i++)a[i]=s[i]-'0';
return a;
}
int l[M],r[M],h[N],cnt;
bs w[M];
inline void add(int id,int tim){
++cnt;
w[cnt]=b[id];
l[cnt]=tim;
r[cnt]=q;
r[h[id]]=tim-1;
h[id]=cnt;
}
int id[M],rig[N];
inline bool cmp(const int &a,const int &b){
return l[a]<l[b];
}
bs bas[N];
inline void ins(bs v,int r,int l){
for(int i=m-1;~i;i--)if(v[i]){
if(rig[i]<l){rig[i]=r;bas[i]=v;return;}
if(rig[i]<r)swap(rig[i],r),swap(v,bas[i]);
v^=bas[i];
}
}
inline bs qry(int tim){
bs ret;
for(int i=m-1;~i;i--)if(rig[i]>=tim&&!ret[i])
ret^=bas[i];
return ret;
}
bool isq[N];
int main(){
freopen(FIO".in","r",stdin);
freopen(FIO".out","w",stdout);
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=n;i++){
a[i]=rd();
b[i]=a[i]^a[i-1];
add(i,1);
}
for(int i=1;i<=q;i++){
int opt,x,y;
bs w;
scanf("%d",&opt);
switch(opt){
case 1:{
scanf("%d%d",&x,&y);w=rd();
for(int j=x;j<=y;j++)
a[j]^=w;
b[x]^=w;
add(x,i);
if(y^n){
b[y+1]^=w;
add(y+1,i);
}
break;
}
case 2:{
scanf("%d%d",&x,&y);w=rd();
for(int j=x;j<=y;j++){
a[j]=w;
if(j>x&&h[j]){
r[h[j]]=i-1;
b[j].reset();
h[j]=0;
}
}
b[x]=w^a[x-1];
add(x,i);
if(y^n){
b[y+1]=w^a[y+1];
add(y+1,i);
}
break;
}
case 3:{
isq[i]=1;
break;
}
}
}
for(int i=1;i<=cnt;i++)id[i]=i;
sort(id+1,id+cnt+1,cmp);
for(int i=1,j=1;i<=q;i++){
while(j<=cnt&&l[id[j]]<=i)ins(w[id[j]],r[id[j]],i),j++;
if(isq[i]){
bs ans=qry(i);
for(int i=m-1;~i;i--)printf("%d",(int)ans[i]);
puts("");
}
}
return 0;
}
|
方法三
以上两种方法都需要离线，我们考虑一个在线做法：
对于每个基向量，维护其是由那些向量构成的（如果插入失败即这个向量能用之前的一些向量表示同样记录它是由那些表示的，即记录哪些之前的向量异或当前的可以得到
）
每次删除向量
时考虑分类讨论
- 如果存在之前的某个 的构成包含
，则用构成那个
的其他的向量代替出现在其他基或其他 向量中的 比如之前有 （其中 是某个基的向量， 是某个插入失败的向量）那么比如要删除
，由左式得到 ，把所有 出现的地方换成 再删掉这个 即可（这个 就相当于代替了 的作用，并且由于
被删除，这个式子不能再用来把其他项换回来）（比如把 换成 ）
- 如果不存在某个包含 的 可以被 和 表示出来，那么
被删除后一定会降秩。找到最低的包含 的基向量，把其他高于它也包含
的异或上这一个基向量（它们对应的向量的构成也要异或），这样其他的基所表示的东西不变（一个基向量异或另一个基向量前后总的线性空间大小肯定不变），且只有这一个基向量含有
了，那么就只删除这一个基就行。（这里不用考虑 向量因为到了这一步就说明没有包含 的 ）
刚才那题的用这个写法实现在线，可以见 https://www.cnblogs.com/daklqw/p/11545965.html
然后有道强制在线的题：UOJ453
Description
给定 的 矩阵 ，求有多少对分别是 和 的 矩阵 、 满足
有 组询问， 每个询问会对 的一行进行修改并求答案，强制在线
Constraints
Solution
左乘一个矩阵相当于对矩阵进行行线性变换，右乘一个矩阵相当于对矩阵进行列线性变换
发现答案只与
的秩有关，两个秩相同的
的答案可以相互转换一一对应，算出所有 的秩为 的答案之和再除以秩为 的矩阵个数就是答案
对于一特定的秩为 的矩阵 和特定的矩阵 ，矩阵 的每一列就对应一个 线性变换到 的那一列的方法，对于特定的 和 的这一列， 这一列的方案数是 。 每一列都是这样，一共有 列，得到对于特定的矩阵 和 ， 的方案数是
设 行 列秩为 的矩阵数为
转移大概是
但我们知道对于 秩为
的矩阵 ，进行列线性变换后变成 的矩阵时秩不一定还等于
考虑计算 的秩是 时有多少种秩为 的 可以由 经过列线性变换得到
有个不会证的定理
的列满秩（秩为 ）矩阵乘上 的矩阵得到的 的矩阵的秩等于这个 的矩阵的秩
把左边列满秩的 行 列矩阵看成是 行 列（只是最后有 列全是
），那么考虑所有列的线性变换就是一个任意的 行 列的矩阵。但是（线性变换矩阵的）最后的
行没有意义因为左边只有前 列有值，最后 列全是 。所以线性变换矩阵只有前 行有用相当于一个 行 列的矩阵。由于我们要算乘出来 行 列秩为
的矩阵有多少种情况，由之前的定理得到就是这个 行 列的秩为 的情况数。
所以答案就是
带修改就是动态维护线性基的秩，照着上面的搞法做就行
可以记录一个
表示第 个基向量（这个 只是从前往后的第 个，是个标号跟它是哪一位的基无关）在第
位和第 位的基向量放在了第 个。
如果 就代表第
个基向量没有插入任何一位，用它来替换其他的位置就行（相当于不用分类讨论，每次只要找含有
的 最小的
把它删了就行，如果它是个基再把秩数减一即可）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
| #include<bits/stdc++.h>
#define ll long long
#define FIO "uoj453"
using namespace std;
const int N=1e3+5,MOD=1000000007;
inline int add(int a,const int &b){return (a+=b)>=MOD?a-MOD:a;}
inline int sub(int a,const int &b){return (a-=b)< 0?a+MOD:a;}
inline int mul(const int &a,const int &b){return 1ll*a*b%MOD;}
inline int& inc(int &a,const int &b){return a=add(a,b);}
inline int& dec(int &a,const int &b){return a=sub(a,b);}
inline int& pro(int &a,const int &b){return a=mul(a,b);}
inline int qpow(int a,int b){int c=1;for(;b;b>>=1,pro(a,a))if(b&1)pro(c,a);return c;}
#define bs bitset<N>
int p,q,s,m,k;
int bin[N];
int ans[N],fp[N][N],fs[N][N];
bs C[N];
int rk;
inline bs rd(){
bs ret;
for(int i=1,x;i<=s;i++){
scanf("%d",&x);
ret[i]=x;
}
return ret;
}
bs id[N];
int pos[N],rnk[N];
inline void ins(int x){
pos[x]=0;
for(int i=s;i;i--)if(C[x][i]){
if(!rnk[i]){
rnk[i]=x;
rk++;
pos[x]=i;
break;
}
id[x]^=id[rnk[i]];
C[x]^=C[rnk[i]];
}
}
inline int erase(int x){
int mn=s+1,now=0;
for(int i=1;i<=p;i++)if(id[i][x]&&pos[i]<mn)now=i,mn=pos[i];
for(int i=1;i<=p;i++)if(id[i][x]&&i^now)C[i]^=C[now],id[i]^=id[now];
if(pos[now])rk--,rnk[pos[now]]=0,pos[now]=0;
C[now].reset();id[now].reset();
return now;
}
int main(){
freopen(FIO".in","r",stdin);
freopen(FIO".out","w",stdout);
scanf("%d%d%d%d%d",&p,&q,&s,&m,&k);
for(int i=1;i<=p;i++)
C[i]=rd(),id[i][i]=1,ins(i);
bin[0]=1;for(int i=1;i<N;i++)bin[i]=mul(bin[i-1],2);
fp[0][0]=fs[0][0]=1;
for(int i=1;i<N;i++){
for(int j=0;j<=min(i,p);j++){
fp[i][j]=mul(fp[i-1][j],bin[j]);
if(j)inc(fp[i][j],mul(fp[i-1][j-1],sub(bin[p],bin[j-1])));
}
for(int j=0;j<=min(i,s);j++){
fs[i][j]=mul(fs[i-1][j],bin[j]);
if(j)inc(fs[i][j],mul(fs[i-1][j-1],sub(bin[s],bin[j-1])));
}
}
for(int r=1;r<=min(p,q);r++){
for(int x=r;x<=min(p,q);x++)
inc(ans[r],mul(fp[q][x],mul(fs[x][r],qpow(2,(q-x)*s))));
pro(ans[r],qpow(fp[s][r],MOD-2));
}
int lst;
printf("%d\n",lst=ans[rk]);
while(m--){
int j,x;
scanf("%d",&j);
j=j^(k*lst);
x=erase(j);
C[x]=rd();
id[x][j]=1;
ins(x);
printf("%d\n",lst=ans[rk]);
}
return 0;
}
|
只选偶数的线性基
比如一个矩阵只能选偶数个位置可以将所有横着或者竖着相邻的位置对插入这样一定异或出来是有偶数个有值。如果要选奇数个就最开始加入一个只有一个格子的。
对于有特殊性质的线性基的奇怪写法
比如一列最多只有两个
的情况每个向量只能选或不选，求最后异或出来为 的方案数
把有两个
的看成是两个对应列连的一条边，把只有一个 的看成是对应点上的权值
最后会形成若干个连通块使用并查集维护每个连通块的点数、边数和权值。
假设现在有一个 个点 条边点上的权值和是 的连通块，分类讨论：
：那么这个连通块的矩阵就不满秩，只能像上面所说的表示出所有选偶数的情况。这时我们取
条边的
条形成一个树（必定能找到不然就不是一个连通块），其他任意的边的加入都可以由这
条树边对应的向量异或出来，所以答案就是除了 条边的其他任选的方案：
：除了那 条可以任意表示剩余 条边的情况外还有
个可以单点翻转的，但是不能翻转奇数个否则无法消成 ，而任意偶数次都可以。我们可以任选前
个单点的情况最后一个根据前面的奇偶性来选/不选，所以答案是
