动态线性基学习笔记
August 16, 2019

动态线性基可以维护一个集合，支持修改集合元素，并查询子集最大异或和。

「雅礼集训2017」PATH
July 20, 2019

给定 nn 和 {ai}\{a_i\}，满足 a0≥a1≥⋯≥an−1≥0a_0 \geq a_1 \geq \cdots \geq a_{n - 1} \geq 0，求出在 nn 维空间中从 (0,0,…,0)(0, 0, \ldots, 0) 走到 (a0,a1,…,an−1)(a_0, a_1, \ldots, a_{n - 1})，每一步使某一维坐标增加 11 的方案中随机选出一种，满足经过的所有点 (x0,x1,…,xn−1)(x_0, x_1, \ldots, x_{n - 1}) 都满足 x0≥x1≥⋯≥xn−1x_0 \geq x_1 \geq \cdots \geq x_{n - 1} 的概率，答案模 10045358091004535809 输出。

n,ai≤5×105n, a_i \leq 5\times 10^5。

「CF1053E」Euler tour
May 09, 2019

给定一棵树的欧拉序，其中被若干位被删除。你可以在被删除的位置填数，要求构造任何一个合法的欧拉序。

n≤5×105,∣S∣=2n−1n \leq 5 \times 10^5, |S| = 2n - 1。

「HNOI2019」白兔之舞
April 08, 2019

有一张顶点数为 (L+1)×n(L+1)\times n 的有向图。这张图的每个顶点由一个二元组(u,v)(u,v)表示(0≤u≤L,1≤v≤n)(0\le u\le L,1\le v\le n)。 这张图不是简单图，对于任意两个顶点 (u1,v1)(u2,v2)(u_1,v_1)(u_2,v_2)，如果 u1<u2u_1<u_2，则从 (u1,v1)(u_1,v_1) 到 (u2,v2)(u_2,v_2) 一共有 w[v1][v2]w[v_1][v_2] 条不同的边，如果 u1≥u2u_1\ge u_2 则没有边。

白兔将在这张图上上演一支舞曲。白兔初始时位于该有向图的顶点 (0,x)(0,x)。

白兔将会跳若干步。每一步，白兔会从当前顶点沿任意一条出边跳到下一个顶点。白兔可以在任意时候停止跳舞（也可以没有跳就直接结束）。当到达第一维为 LL 的顶点就不得不停止，因为该顶点没有出边。

假设白兔停止时，跳了 mm 步，白兔会把这只舞曲给记录下来成为一个序列。序列的第 ii 个元素为它第 ii 步经过的边。

问题来了：给定正整数 kk 和 yy（1≤y≤n1\le y\le n），对于每个 tt（0≤t<k0\le t<k），求有多少种舞曲（假设其长度为 mm）满足 m mod k=tm \bmod k=t，且白兔最后停在了坐标第二维为 yy 的顶点？

两支舞曲不同定义为它们的长度（mm）不同或者存在某一步它们所走的边不同。

1≤n≤3, 1≤k≤65536, 108≤p≤2301 \leq n \leq 3,\ 1 \leq k \leq 65536,\ 10^8 \leq p \leq 2^{30}。