文章目錄

• 解析
• 實(shí)現(xiàn)
• 刪除

所謂線性基，就是線性的基

（逃）

解析

何為線性基？
定義幾何$B$為集合$S$的線性基,當(dāng)且僅當(dāng):

.S任意子集異或和可以得到的結(jié)果，用B的子集都也可以得到，且B時所有這樣的集合中元素最少的

線性基的一些重要的性質(zhì)

1.線性基沒有異或和為 0 的子集。
2.線性基中每個元素的異或方案唯一，也就是說，線性基中不同的異或組合異或出的數(shù)都是不一樣的。
3.線性基中每個元素的二進(jìn)制最高位互不相同。

實(shí)現(xiàn)

累了
不想打字了
而且我也說不明白
大概就是利用異或的交換律的性質(zhì)balabala
利用之前的和自己合體拼出S的所有元素
直接看代碼吧

void solve(){mi[0]=1;for(int i=1;i<=50;i++){mi[i]=mi[i-1]*2;//printf("i=%d mi=%lld\n",i,mi[i]);}for(int o=1;o<=n;o++){ll x=a[o];//printf("o=%d x=%lld\n",o,x);int flag=0;for(int i=50;i>=0;i--){if((x&mi[i])==0) continue;else if(!p[i]){p[i]=x;break;}else{x^=p[i];}}} }

刪除

有一個集合 $S$，要求支持加數(shù)和刪除，動態(tài)維護(hù)線性基。

對于刪除一個數(shù) $x$，分類討論：
如果 $x$ 不在線性基內(nèi)：直接把這個數(shù)刪掉即可。
如果這個數(shù)在線性基內(nèi)：設(shè)每個元素在嘗試插入線性基時異或的線性基的集合為 $P$，那么如果存在一個線性基外的元素 $y$ 的 $P$ 集合包含 $x$，說明這兩個元素是等價的，直接把那個元素刪去即可；否則，不僅要刪除 $x$，還要去除其他元素異或 $x$ 的影響，設(shè)在線性基內(nèi)且 $P$ 集合包含 $x$ 的最小元素為 $y$，則令 $x\oplus y$ 取代 $x$ 元素，并另其他在線性基內(nèi)且 $P$ 集合包含 $x$ 的元素異或上 $y$。

可以離線時，線段樹分治還是很香的。

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的模板：线性基的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。