「CF917D」Stranger Trees
给出一棵大小为 n 的树。
对于每个 k (0 \leq k \leq n - 1),你需要求出有多少个大小为 n 的带标号树与原树有恰好 k 条重合的边。答案对 10^9 + 7 取模。
数据范围:1 \leq n \leq 100。
时空限制:1s / 250MiB。
给出一棵大小为 n 的树。
对于每个 k (0 \leq k \leq n - 1),你需要求出有多少个大小为 n 的带标号树与原树有恰好 k 条重合的边。答案对 10^9 + 7 取模。
数据范围:1 \leq n \leq 100。
时空限制:1s / 250MiB。
给出一棵包含 n 个节点的树。你需要给每个节点染上数字 0 或 1。
路径 (u, v) 的权值,等于从 u 到 v 的最短路径上所有节点数字的 MEX。一种染色方案的权值等于所有 1 \leq u \leq v \leq n 的路径 (u, v) 的权值之和。
请求出所有的染色方案中,可能的最大权值。
数据范围:1 \leq n \leq 2 \times 10^5。
时空限制:3s / 256MiB。
给出一张包含 n 个点 m 条边的无向图,每个点有一个颜色 c_i (1 \leq c_i \leq k),求有多少组颜色对 a, b (a < b) 满足保留颜色为 a 或 b 的节点的导出子图是二分图。
数据范围:1 \leq n \leq 5 \times 10^5,0 \leq m \leq 5 \times 10^5,2 \leq k \leq 5 \times 10^5。
时空限制:3s / 500MiB。
给出一个长度为 n 的数组 a,你需要找出字典序最大的子序列 s,使得 s 可以作为多边形的边长。
当且仅当 |s| \geq 3 且满足以下条件时,s 可以作为多边形的边长
数据范围:3 \leq n \leq 2 \times 10^5,1 \leq a_i \leq 10^9。
时空限制:3s / 250MiB。
给出一棵包含 n 个点的树,编号 1 \sim n。第 i 个点的高度为 h_i。
你可以在任意点放置任意数量的塔,对于每个塔,你可以选择放在哪个点,并且可以选择它的效率。设置一个效率为 e 的塔需要花费 e 金币,其中 e > 0。
如果存在一对分别位于 u, v (u \neq v) 的信号塔,它们的效率分别为 e_u, e_v,且满足 \min(e_u, e_v) \geq h_x,且点 x 位于从 u 到 v 的路径上,则我们认为 x 能够收到信号。
请你求出使得所有顶点都接收到信号,所需的最小金币数。
数据范围:2 \leq n \leq 2 \times 10^5,1 \leq h_i \leq 10^9。
时空限制:2s / 256MiB。
给出一个长度为 n 的序列 a,仅由 0 或 1 构成。
你需要对序列进行至多 n 次操作(或者说明这是不可能的),每次操作你可以选择一个下标 i (1 \leq i \leq n - 2),然后将 a_i, a_{i + 1}, a_{i + 2} 均改成 a_i \oplus a_{i + 1} \oplus a_{i + 2}。
数据范围:3 \leq n \leq 2 \times 10^5,0 \leq a_i \leq 1。
时空限制:1s / 256MiB。
有 p 个人玩一个游戏,第 i 个人的得分为 a_i。
已知 \sum a_i = s 且 a_1 \geq r,得分最高的人可以获胜,若多个人得分最高,则等概率随机其中一个人获胜。
求第一个人获胜的概率,答案对 998244353 取模。
数据范围:1 \leq p \leq 100,0 \leq r \leq s \leq 5000。
时空限制:3s / 250MiB。
给出一棵包含 n 个点的树。
有 Q 次询问,每次询问给出三个整数 k, m, r,随后给出 k 个树上的节点 a_1, a_2, \dots, a_k。假设树的根为 r,我们需要将这 k 个节点划分成至多 m 组,并且:
你需要求出分组的方案数,答案对 10^9 + 7 取模。
数据范围:1 \leq n, Q \leq 10^5,1 \leq k, r \leq n,1 \leq m \leq \min(300, k),1 \leq \sum k \leq 10^5。
时空限制:1.5s / 256MiB。
维护 n 个初始为空的可重集。有 Q 次操作,每次操作形如以下四种之一:
1 x v:令集合 x 等于 \{v\}。2 x y z:令集合 x 等于集合 y 与 z 的并。3 x y z:令集合 x 等于集合 y 与 z 的积,A \times B = \{\gcd(a, b) \mid a \in A, b \in B\}。4 x v:询问 v 在集合 x 中出现次数模 2 的结果。数据范围:1 \leq n \leq 10^5,1 \leq q \leq 10^6,1 \leq v \leq 7000。
时空限制:3s / 250MiB。
给出一个长度为 n 的数组 a,记 s_i = \sum_{j = 1}^i a_j。
有 Q 次操作,每次操作给出两个整数 p, x,表示将 a_p 赋成 x。每次操作后,你都需要判断是否存在一个位置 i 满足 a_i = s_{i - 1}。若存在,输出任意一个满足条件的 i。
数据范围:1 \leq n, Q \leq 2\times 10^5,0 \leq a_i \leq 10^9,1 \leq p \leq n,0 \leq x \leq 10^9。
时空限制:3s / 256MiB。