Linear basis

Linear basis is a relatively easy to learn but may not be useful algorithm.

Below are two blogs that I think are better.

Linear-based talk

Detailed Explanation of Linear Base

The complexity of the linear basis is very good, if it is inserted normally, it is \(O(n*64)\), and millions of data are run randomly.

The most important thing about a linear basis is its several excellent properties, which are generally investigated in the topic of a linear basis.

The value range of the XOR of the numbers in the original number set is equal to the value range of the elements in the linear basis.

This is very important, indicating that the linear basis can replace the original number set for the next step, and it is also a guarantee for the correctness of the linear basis.
Linear basis is simplified, not redundant.

This means that the linear basis is the smallest set of numbers that satisfies the conditions, and there are not too many. Specifically, there are several small properties:

There is no non-empty subset whose XOR sum is zero in the linear basis.

Each scheme of the selected element in the linear basis corresponds to an XOR value, and there is no situation where multiple selection schemes correspond to the same XOR value

The above are the two major properties of linear basis, which are the basis of linear basis.

Regarding the question, the main difficulty is that it is difficult for you to think that this is a linear basis question. Generally speaking, it is not difficult after thinking it.

Basic use of supplementary linear basis:

Query the maximum value of the exclusive OR of n numbers.
Query the minimum value of the exclusive OR of n numbers.
Query whether a certain number can be XORed.
Query the k small value of the exclusive OR of n numbers.

巴特西

Linear basis

Linear-based talk

Detailed Explanation of Linear Base

最新文章

热门文章