CCPC赛后补题-线性基

模板题：https://www.luogu.com.cn/problem/P3812

线性基可以用一个长度为$ \log_2N $的数组描述值域[1,N]，0的情况需要特判。

• 一个长度为64的线性基可以描述所有的64位整数。

在2024年CCPC网络赛中，考到了线性基。没学过，追悔莫及。

• https://codeforces.com/gym/105336

原题需要在不污染高位的情况下，找到尽可能最优的二进制串修改低位，使得两个二进制串的最大值最小。

处理这种找最优串的问题，我能想到的只有字典树，而字典树在本题中非常乏力：会污染高位，必须要在O(1)的时间内找到最优串。

线性基模板的函数包括：

• void ins(int x)：向线性基数组中插入x
• bool check(int x)：判断x是否可以由线性基构造
• int qmin()：查询当前线性基可以构造的最小值
• int qmax()：查询当前线性基可以构造的最大值
• void rebuild()：重构线性基，使得每一位尽可能少地影响其它位
• int kth(int k)：查询线性基可以构造的第k小的数
• int qrank(int x)：查询x是线性基可以构造的第几小的数

全局变量包括：

• const int MN=64：线性基数组的长度
• int p[MN]：存储线性基
• int d[MN]：存储有效势，也就是数组p[]中的非0值
• int cnt：线性基的维数、势、元素个数，同时为d[]的有效长度

线性基数组的第i in [0,MN-1]位，表示的是，最高位是第i位的01串。

• 当想要构造一个第i位是1的串时，可以异或，线性基数组的第i位。

在插入和查询时，从高位向低位枚举，因为高位的势会影响低位，对低位造成的影响在枚举到低位时，由低位的势处理。

线性基板子

talk is cheap show me the code：

#define int long long
using namespace std;
const int MN=64;int p[MN],d[MN],cnt;void ins(int x) {for(int i=MN-1; i>=0; i--) {if(x>>i&1) {if(p[i])x^=p[i];else {p[i]=x;return;}}}
}
bool check(int x) {for(int i=MN-1; i>=0; i--) {if(x>>i&1) {if(p[i])x^=p[i];else return false;}}return true;
}int qmin() {for(int i=0; i<MN-1; i++) {if(p[i])return p[i];}return 0;
}int qmax() {int res=0;for(int i=MN-1; i>=0; i--) {res=max(res,res^p[i]);}return res;
}void rebuild() {cnt=0;for(int i=MN-1; i>=0; i--)for(int j=i-1; j>=0; j--)if(p[i]&1ll<<j)p[i]^=p[j];for(int i=0; i<MN; i++)if(p[i])d[cnt++]=p[i];
}int kth(int k) {if(k>=1ll<<cnt)return -1;int ans=0;for(int i=MN-1; i>=0; i--)if(k>>i&1)ans^=d[i];return ans;
}int qrank(int x) {int ans=0;for(int i=cnt-1; i>=0; i--) {if(x>=d[i]) {ans+=1<<i;x^=d[i];}}return ans;
}

AC代码

• https://codeforces.com/gym/105336/submission/280725694

赛后补题，WA10😭：

WA的原因包括：

• 插入线性基忘了return
• 没关闭流同步超时
• 用(a&1<<i)==1判1
• 第一个无法抹掉的1有两种可能，需要封装函数