August 16, 2019

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

July 20, 2019

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

n,ai5×105n, a_i \leq 5\times 10^5

April 08, 2019

有一张顶点数为 (L+1)×n(L+1)\times n 的有向图。这张图的每个顶点由一个二元组(u,v)(u,v)表示(0uL,1vn)(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] 条不同的边,如果 u1u2u_1\ge u_2 则没有边。

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

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

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

问题来了:给定正整数 kkyy1yn1\le y\le n),对于每个 tt0t<k0\le t<k),求有多少种舞曲(假设其长度为 mm)满足 mmodk=tm \bmod k=t,且白兔最后停在了坐标第二维为 yy 的顶点?

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

1n3, 1k65536, 108p2301 \leq n \leq 3,\ 1 \leq k \leq 65536,\ 10^8 \leq p \leq 2^{30}