10.3
Codeforces Round #746 (Div. 2)
A
1 |
|
B
1 |
|
C
1 |
|
10.4
Lindström–Gessel–Viennot lemma，可以用来处理$ $上不相交路径计数等问题。
\(\omega(P)\) 表示 \(P\) 这条路径上所有边的边权之积。（路径计数时，可以将边权都设为 \(1\)）（事实上，边权可以为生成函数）
\(e(u, v)\) 表示 \(u\) 到 \(v\) 的$ $ \(P\) 的 \(\omega(P)\) 之和，即 \(e(u, v)=\sum\limits_{P:u\rightarrow v}\omega(P)\)。
起点集合 \(A\)，是有向无环图点集的一个子集，大小为 \(n\)。
终点集合 \(B\)，也是有向无环图点集的一个子集，大小也为 \(n\)。
一组 \(A\rightarrow B\) 的不相交路径 \(S\)：\(S_i\) 是一条从 \(A_i\) 到 \(B_{\sigma(S)_i}\) 的路径（\(\sigma(S)\) 是一个排列），对于任何 \(i\ne j\)，\(S_i\) 和 \(S_j\) 没有公共顶点。
\(N(\sigma)\) 表示排列 \(\sigma\) 的逆序对个数。
\[ M = \begin{bmatrix}e(A_1,B_1)&e(A_1,B_2)&\cdots&e(A_1,B_n)\\ e(A_2,B_1)&e(A_2,B_2)&\cdots&e(A_2,B_n)\\ \vdots&\vdots&\ddots&\vdots\\ e(A_n,B_1)&e(A_n,B_2)&\cdots&e(A_n,B_n)\end{bmatrix} \]
\[ \det(M)=\sum\limits_{S:A\rightarrow B}(-1)^{N(\sigma(S))}\prod\limits_{i=1}^n \omega(S_i) \]
其中 \(\sum\limits_{S:A\rightarrow B}\) 表示满足上文要求的 \(A\rightarrow B\) 的每一组不相交路径 \(S\)。
路径计数时，\(\omega(S_i)=1\),故\(\prod\limits_{i=1}^n \omega(S_i)=1\)。
例题题意：有一个 \(n\times n\) 的棋盘，棋子只能向下向右走，有 \(m\) 个棋子，一开始第 \(i\) 个棋子放在 \((1, a_i)\)，最终要到 \((n, b_i)\)，路径要两两不相交，求方案数。
观察到如果路径不相交就一定是 \(a_i\) 到 \(b_i\)，因此 LGV 引理中一定有 \(\sigma(S)_i=i\)，不需要考虑符号问题。边权设为 \(1\)，直接套用引理即可。
从 \((1, a_i)\) 到 \((n, b_j)\) 的路径条数相当于从 \(n-1+b_j-a_i\) 步中选 \(n-1\) 步向下走，所以 \(e(A_i, B_j)=\binom{n-1+b_j-a_i}{n-1}\)。
1 | const int M=105,N=2e6+6; |
10.5
用于处理$ \(的多源最短路问题。套用斐波那契堆优化的Dijkstra时间复杂度为\)O(V^2logV+VE)\(,套用二叉堆优化的Dijkstra时间复杂度\)O(VElogE)$。
（稠密图\(V^2\approx E\)，使用Floyd算法即可，无负边权直接做\(V\)次Dijkstra。）
设虚拟结点，与其他点建边权为0的边，从虚拟结点跑spfa得\(h_i\)，重建图赋值\((u, v)\)边权\(w(u, v)\)为\(w(u, v)+h_u-h_v\)，这保证了最短路径不变而且所有权重均非负，跑n次Dijkstra求最短路，算法求得距离为\(dis(s, t)\)，非不可达点的实际距离为\(dis(s, t)-(h_s-h_t)\)。
1 | const int M=6e3+5,N=3e3+5,inf=1e9; |
10.7
$ \(:给定域\)F\(，\)F\(上的向量空间\)V$是一个集合，其上定义加法和数乘运算且这两个运算满足八个公理。
$ \(:对于向量空间中\)V\(上\)n\(个元素的向量组\)(_1, , _n)$,若存在不全为\(0\)的数\(a_i \in F\)满足 \[ a_{1}\mathbf{v}_{1}+a_{2}\mathbf {v}_{2}+\ldots +a_{n}\mathbf{v}_{n} = 0 \]
则称这\(n\)个向量线性相关（linearly dependent），否则称为线性无关（linearly independent）。
$ \(:对于向量空间中 VV 上 nn 个元素的向量组\)(_1, , _n)$，其线性组合（linear combination）是如下形式的向量
\[ a_{1}\mathbf{v}_{1} + a_{2}\mathbf {v} _{2}+\ldots +a_{n}\mathbf {v} _{n} \] 其中\(a_1, \ldots, a_n \in F\)
一组向量线性无关 \(\Leftrightarrow\)没有向量可用有限个其他向量的线性组合所表示
$ $:对于向量空间中 \(V\) 上 \(n\) 个元素的向量组 \((\mathbf{v}_1, \ldots, \mathbf{v}_n)\)，其所有线性组合所构成的集合称为 \((\mathbf{v}_1, \ldots, \mathbf{v}_n)\)的张成（span），记为 \(\mathrm{span}(\mathbf{v}_1, \ldots, \mathbf{v}_n)\)
$ $:若向量空间 \(V\) 中向量组 \(\mathfrak{B}\) 既是线性无关的又可以张成 \(V\)，则称其为\(V\) 的基（basis）。
\(\mathfrak{B}\)中的元素称为基向量。如果基中元素个数有限，就称向量空间为有限维向量空间，将元素的个数称作向量空间的维数。
设 \(\mathfrak {B}\) 是向量空间 \(V\) 的基。则\(\mathfrak {B}\)具有以下性质：
1.\(V\) 是 \(\mathfrak {B}\)的极小生成集，就是说只有\(\mathfrak {B}\)能张成\(V\)，而它的任何真子集都不张成全部的向量空间。
2.\(\mathfrak {B}\) 是 \(V\) 中线性无关向量的极大集合，就是说 \(\mathfrak {B}\) 在\(V\) 中是线性无关集合，而且\(V\) 中没有其他线性无关集合包含它作为真子集。
3.\(V\) 中所有的向量都可以按唯一的方式表达为\(\mathfrak {B}\) 中向量的线性组合。
$ $
对于数 \(a_0, a_1, \ldots, a_n\)，将 \(a_i\)的二进制表示$ (b_{m}b_0)_2$ 看作一个向量。向量组 \(\mathbf{a}_1, \ldots, \mathbf{a}_n\)可以张成一个向量集合 \(\mathrm{span}(\mathbf{a}_1, \ldots, \mathbf{a}_n)\)，加上我们的异或运算和乘法运算（显然满足 8 条公理），即可形成一个向量空间 \(V = (\{0, 1\}, \mathrm{span}(\mathbf{a}_1, \ldots, \mathbf{a}_n), \oplus, \cdot)\)
设集合\(S\)中最大的数在二进制意义下有\(L\)位，我们使用一个 \([0\dots L]\)的数组\(a\)来储存线性基。
这种线性基的构造方法保证了一个特殊性质，对于每一个\(i\),\(a_i\)有以下两种可能：（如果排成矩阵，形成一个下三角矩阵）
1 | typedef long long ll; |
最大异或和：将线性基中所有向量异或起来得到的向量所对应的数。
1 | ll querymax(){ |
集合任选大于1个元素异或出的第k大数
1 | vector<ll> v; |
10.8
P4151 [WC2011]最大XOR和路径
异或路径问题：转化成任意一条路径，和任意个圈的异或。
1 |
|
P4301 [CQOI2013] 新Nim游戏
1 |
|
P3292 [SCOI2016]幸运数字
1 |
|
10.9
Codeforces Round #747 (Div. 2)
A
1 |
|
B
1 |
|
C
1 |
|
E1
1 |
|
E2
1 |
|