一个小题目

这应该是某道题的弱化版。

题目就是给定一个正整数序列,长度 \leqslant 3 \times 10^5 ,然后值域是到 [1,10^9]

q 个询问 (q \leqslant 3 \times 10^5) ,每次呢给定一个数字 w (值域还是 [1,10^9] ),和区间 [l,r]

然后你可以把 w 异或上序列的 [l,r] 内的任意数字任意次。

要求最后的 w' 最小。

 

那么我们先来思考一个简单点的问题。如果是给定整个序列,那么我们可以预处理出序列的线性基

然后可以做到 O(\log_2 10^9) 内回答一个询问。

具体做法就是从高到低地,如果这一位非零,那就异或这一位的线性基然后继续下一位。

 

那么下面我们说一下线性基合并。线性基合并就是把其中一个线性基暴力地插入另一个线性基。

这样做的复杂度是 O(\log_2^2 10^9) 的。

那么我们可以用线段树/ST表等任意 \log 区间数据结构去维护线性基合并。

建议用ST表,这样预处理尽管带了三个 \log ,但是回答却是两个 \log 的,而且比线段树常数小。

 

可是有什么方法把整个算法也从三个变为两个 \log 呢?

分治!把回答离线,先递归处理掉左右两侧的回答,再处理跨中线的回答就好了。

每次返回的时候都合并一下。

 

那么还有一个相关的问题,和这种无关的。

把刚刚的问题修改一下,我们只能选择区间内的任意数字然后异或一次。

oh!可持久化Trie!

每次递归地往下走就好了。

非常好写。

乱写点线代

UPD:刚买了本线代,感觉还挺好的,学几页之后会在这里补充一些想法和笔记。

 

矩阵都会吧……基础的加减法

矩阵转置满足:

\begin{array}{l} \left( A^T \right) ^T=A \\\\ \left( \lambda A \right) ^T=\lambda A^T \\\\ \left( AB \right) ^T=B^TA^T \\\\ \end{array}


矩阵乘法(提高组内容)

\begin{array}{l} C_{mn}=A_{mp}\times B_{pn} \\ C_{ij}=\sum_{k=1}^p{a_{ik}b_{kj}} \\ \end{array}


一些常见的规律

\begin{array}{l} A\left( BC \right) =\left( AB \right) C \\ \left( A+B \right) C=AC+BC \\ C\left( A+B \right) =CA+CB \\ \lambda \left( AB \right) =\left( \lambda A \right) B=A\left( \lambda B \right) \\ \end{array}


Hadamard积

没见过这玩意

以下是运算定义

\left( A\ast B \right) _{ij}=a_{ij}b_{ij}


Kronecker积

神奇。

\left( \begin{matrix} 1& 2\\ 3& 4 \end{matrix} \right) \otimes \left( \begin{matrix} 5& 6\\ 7& 8 \end{matrix} \right) =\left( \begin{matrix} 1\cdot 5& 1\cdot 6& 2\cdot 5& 2\cdot 6\\ 1\cdot 7& 1\cdot 8& 2\cdot 7& 2\cdot 8\\ 3\cdot 5& 3\cdot 6& 4\cdot 5& 4\cdot 6\\ 3\cdot 7& 3\cdot 8& 4\cdot 7& 4\cdot 8 \end{matrix} \right)


一个n阶的行列式的定义是这样的

\det \left( A \right) =\sum_{\left( i_1i_2i_3\cdots i_n \right)}{\delta \left( i_1i_2i_3\cdots i_n \right) a_{1i_i}a_{2i_2}a_{3i_3}\cdots a_{ni_n}=|A|}

其中\delta \left( i_1i_2i_3\cdots i_n \right)

表示排列\left( i_1i_2i_3\cdots i_n \right)中当逆序对个数为t\left(-1\right)^{t}的值


好了,我们考虑一些性质

1.\det \left( A \right) =\det \left( A^T \right)

2.两行互换,行列式变号

3.一行乘上k , 行列式乘上k

4.两个行列式只有一行不同,他们的行列式和等于不同的行相加后的行列式

也记为:若行列式的某一列(行)的元素都是两数之和,则这个行列式是对应两个行列式的和

推论:将行列式的任意行乘以实数k,再相应地加到另一行上去,行列式的值不变

证明推论:拆成两个行列式的和,一个有两行成比例…

5.每行每列和均为0的矩阵行列式为0

·   ·   ·   ·   ·

\det \left( AA^T \right) =\left( \det \left( A \right) \right) ^2


Binet-Cauchy公式

A,B分别为n\times ss\times n矩阵

则有\det \left( AB \right)=

\begin{cases} \text{0\ ,\ }n>s\\ \det \left( A \right) \cdot \det \left( B \right) \ ,\ n=s\\ \sum{\det \left( A_s \right) \det \left( B_s \right)}\ ,n<s \end{cases}

这里面那个A_s通俗的,不严格的定义就是说从A里面s行选任意n行组成的新的矩阵,然后B_s也是类似,最后那个 \sum 就是枚举全部的这样的组合


高斯消元法求解行列式 (在此强烈安利 ATP学姐的高斯消元 )

高斯消元这玩意都会吧……

这儿有些细节

第一是交换两行的时候要对答案取负

第二是要用第j行去减第i行,所得答案作为新的第j行(也就是这里的减法正好相反)

最后求 \det \left( A \right) ,因为根据行列式的定义,recur下去每行只能选主对角的那个(否则一定有一个0)那么就是主对角的乘积。(记得取负之类的)


矩阵树定理

非常奇妙

我们来定义图G的度数矩阵D为一个n \times n的矩阵,当结点i \ne j时,d_{ij}=0 ;  当i=j时,d_{ij}等于i的度数

G的邻接矩阵A,当结点i,j之间有k条边相连的的时候,a_{i,j}=k

现在定义图G的Kirchhoff矩阵C=D-A,那么Matrix-Tree定理告诉我们,图G的生成树个数为C的任意一个n-1阶主子式的绝对值。

关于所谓的n-1阶主子式,也就是一个n阶矩阵除第n行和列之后形成的子矩阵的行列式。


Vfk有一篇关于轮状病毒的题解写的特别妙,在这里安利 1002: [FJOI2007]轮状病毒

然鹅他写的好长…… 😕 哇emoji好可爱


矩阵初等变换,先坑着

法法塔也先坑着