2020-03-27算法竞赛/题解
给定 nnn 次多项式 f(x)=∑i=0naixif(x) = \sum_{i=0}^n a_i x^if(x)=i=0∑naixi QQQ 次询问，第 iii 次询问 f(qi)f(q_i)f(qi) 对 998244353998244353998244353 取模的值。 其中 qiq_iqi 是一个一阶线性递推，给定 q0,x,yq_0, x, yq0,x,y ，满足 qn=xqn−1+yq_n = x q_{n-1} + yqn=xqn−1+y 1≤n≤2.5×105, 1≤Q≤106, 2≤x<998244353, 0≤q0,y<9982443531 \leq n \leq 2.5 \times 10^5, \ 1 \leq Q \leq 10^6, \ 2 \leq x < 998244353, \ 0 \leq q_0, y < 9982443531≤n≤2.5×105, 1≤Q≤106, 2≤x<998244353, 0≤q0,y<998244353 。
给定 nnn 次多项式
QQQ 次询问，第 iii 次询问 f(qi)f(q_i)f(qi) 对 998244353998244353998244353 取模的值。
其中 qiq_iqi 是一个一阶线性递推，给定 q0,x,yq_0, x, yq0,x,y ，满足
1≤n≤2.5×105, 1≤Q≤106, 2≤x<998244353, 0≤q0,y<9982443531 \leq n \leq 2.5 \times 10^5, \ 1 \leq Q \leq 10^6, \ 2 \leq x < 998244353, \ 0 \leq q_0, y < 9982443531≤n≤2.5×105, 1≤Q≤106, 2≤x<998244353, 0≤q0,y<998244353 。
2020-03-25算法竞赛/算法笔记
两人在一二分图上进行决策，初始状态为二分图的一个点，两人轮流沿边行动，不允许重复访问节点，无法移动者输。 这样的问题称为二分图博弈。
两人在一二分图上进行决策，初始状态为二分图的一个点，两人轮流沿边行动，不允许重复访问节点，无法移动者输。
这样的问题称为二分图博弈。
2019-12-26算法竞赛/算法笔记
五边形数级数的生成函数即欧拉函数： φ(x)=∏n=1∞(1−xn)\varphi(x) = \prod_{n=1}^\infty (1 - x^n)φ(x)=n=1∏∞(1−xn)
五边形数级数的生成函数即欧拉函数：
2019-11-21算法竞赛/题解
给定一个长度为 nnn 的数组 {ai}i=1n\{a_i\}_{i=1}^n{ai}i=1n，QQQ 次询问，每次给定 lll 和 rrr 查询 lcmi=lrai\operatorname*{lcm}_{i=l}^r a_ilcmi=lrai 答案对 109+710^9+7109+7 取模，多组数据。 T,n,Q≤300, ai≤1018T,n,Q \leq 300,\ a_i \leq 10^{18}T,n,Q≤300, ai≤1018。
给定一个长度为 nnn 的数组 {ai}i=1n\{a_i\}_{i=1}^n{ai}i=1n，QQQ 次询问，每次给定 lll 和 rrr 查询
lcmi=lrai\operatorname*{lcm}_{i=l}^r a_ilcmi=lrai
答案对 109+710^9+7109+7 取模，多组数据。
T,n,Q≤300, ai≤1018T,n,Q \leq 300,\ a_i \leq 10^{18}T,n,Q≤300, ai≤1018。
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。