2019-09-27算法竞赛/算法笔记
本文以矩阵交相关内容为主，忽略掉了大部分证明，感兴趣的读者请自行阅读集训队论文。 拟阵的定义 记 M=(S,L)M = (S, L)M=(S,L) 表示一个定义在有限集 SSS 上，独立集的集合为 LLL 的拟阵。其中 LLL 是 SSS 的一些子集构成的集合。拟阵 MMM 满足以下公理： (遗传性). 如果 I∈L,J⊆II \in L, J \subseteq II∈L,J⊆I，那么 J∈LJ \in LJ∈L。 (交换性). 如果 I,J∈LI,J \in LI,J∈L 且 ∣I∣<∣J∣|I| < |J|∣I∣<∣J∣，那么 ∃x∈J∖I\exists x \in J \setminus I∃x∈J∖I 满足 I∪{x}∈LI \cup \{x\} \in LI∪{x}∈L。 如果 I∈LI \in LI∈L，我们称 III 是独立的，也称 III 是独立集；否则，我们称 III 是不独立的，也成 III 是非独立集。通常，我们认为 ∅\varnothing∅ 是独立的。
本文以矩阵交相关内容为主，忽略掉了大部分证明，感兴趣的读者请自行阅读集训队论文。
记 M=(S,L)M = (S, L)M=(S,L) 表示一个定义在有限集 SSS 上，独立集的集合为 LLL 的拟阵。其中 LLL 是 SSS 的一些子集构成的集合。拟阵 MMM 满足以下公理：
如果 I∈LI \in LI∈L，我们称 III 是独立的，也称 III 是独立集；否则，我们称 III 是不独立的，也成 III 是非独立集。通常，我们认为 ∅\varnothing∅ 是独立的。
2019-08-16算法竞赛/算法笔记
动态线性基可以维护一个集合，支持修改集合元素，并查询子集最大异或和。
2019-07-20算法竞赛/题解
给定长度为 nnn 的序列 {ai}\{a_i\}{ai}，满足 a0≥a1≥⋯≥an−1≥0a_0 \geq a_1 \geq \cdots \geq a_{n - 1} \geq 0a0≥a1≥⋯≥an−1≥0，求出在 nnn 维空间中从点 (0,0,…,0)(0, 0, \ldots, 0)(0,0,…,0) 随机游走到点 (a0,a1,…,an−1)(a_0, a_1, \ldots, a_{n - 1})(a0,a1,…,an−1)，满足经过的所有点 (x0,x1,…,xn−1)(x_0, x_1, \ldots, x_{n - 1})(x0,x1,…,xn−1) 都有 x0≥x1≥⋯≥xn−1x_0 \geq x_1 \geq \cdots \geq x_{n - 1}x0≥x1≥⋯≥xn−1 的概率，随机方式是每一步均匀随机一个 i∈[1,n]∪N+i\in [1,n]\cup \mathbb N_+i∈[1,n]∪N+ 并令 xi:=xi+1x_i:=x_i+1xi:=xi+1。 1≤n,ai≤5×1051\le n, a_i \leq 5\times 10^51≤n,ai≤5×105。答案对 100453580910045358091004535809 取模。
给定长度为 nnn 的序列 {ai}\{a_i\}{ai}，满足 a0≥a1≥⋯≥an−1≥0a_0 \geq a_1 \geq \cdots \geq a_{n - 1} \geq 0a0≥a1≥⋯≥an−1≥0，求出在 nnn 维空间中从点 (0,0,…,0)(0, 0, \ldots, 0)(0,0,…,0) 随机游走到点 (a0,a1,…,an−1)(a_0, a_1, \ldots, a_{n - 1})(a0,a1,…,an−1)，满足经过的所有点 (x0,x1,…,xn−1)(x_0, x_1, \ldots, x_{n - 1})(x0,x1,…,xn−1) 都有 x0≥x1≥⋯≥xn−1x_0 \geq x_1 \geq \cdots \geq x_{n - 1}x0≥x1≥⋯≥xn−1 的概率，随机方式是每一步均匀随机一个 i∈[1,n]∪N+i\in [1,n]\cup \mathbb N_+i∈[1,n]∪N+ 并令 xi:=xi+1x_i:=x_i+1xi:=xi+1。
1≤n,ai≤5×1051\le n, a_i \leq 5\times 10^51≤n,ai≤5×105。答案对 100453580910045358091004535809 取模。
2019-05-09算法竞赛/题解
给定一棵树的欧拉序，其中被若干位被删除。你可以在被删除的位置填数，要求构造任何一个合法的欧拉序。 n≤5×105,∣S∣=2n−1n \leq 5 \times 10^5, |S| = 2n - 1n≤5×105,∣S∣=2n−1。
给定一棵树的欧拉序，其中被若干位被删除。你可以在被删除的位置填数，要求构造任何一个合法的欧拉序。
n≤5×105,∣S∣=2n−1n \leq 5 \times 10^5, |S| = 2n - 1n≤5×105,∣S∣=2n−1。