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。