「Luogu P4389」付公主的背包
有 n 种物品,其中第 i 种物品的体积为 v_i,每一种物品的数量都是无限的。
给出背包的体积上限 m,对于 s \in [1, m],你都需要求出使用这些物品恰好装满 s 体积的方案数。两个方案不同当且仅当存在某个物品的选取个数不同。
数据范围:1 \leq n, m \leq 10^5,1 \leq v_i \leq m。
时空限制:1s / 500MiB。
有 n 种物品,其中第 i 种物品的体积为 v_i,每一种物品的数量都是无限的。
给出背包的体积上限 m,对于 s \in [1, m],你都需要求出使用这些物品恰好装满 s 体积的方案数。两个方案不同当且仅当存在某个物品的选取个数不同。
数据范围:1 \leq n, m \leq 10^5,1 \leq v_i \leq m。
时空限制:1s / 500MiB。
给出一个长度为 n 的序列 a_0, a_1, \dots, a_{n - 1},保证 n 是 2 的若干次幂。
有 Q 次操作,每次操作都形如以下操作中的一种:
1 l r k:对于所有 i \in [l, r),令 b_i = a_{i \oplus k}。然后对于所有 i \in [l, r),令 a_i = b_i。2 l r:求 \sum_{i = l}^{r - 1} a_i 的值。其中 \oplus 表示按位异或。
数据范围:1 \leq n \leq 2^{18},保证 n 是 2 的若干次幂,1 \leq Q \leq 2 \times 10^5,1 \leq a_i \leq 1048576,0 \leq l < r \leq n,0 \leq k < n。
时空限制:2s / 64MiB。
给出一个包含 n 个点的树。
你可以进行若干次操作,每次你可以删除这棵树的一个叶子(即保证剩下部分仍然是连通的)。
你需要求出有多少种删除叶子的方案,使得剩下部分的重心唯一(这里的重心定义与平常相同,即最大子树最小的节点)。
答案对 998244353 取模,两个方案不同当且仅当删除叶子节点构成的集合不同。
数据范围:1 \leq n \leq 3 \times 10^3。
时空限制:3s / 1024MiB。
This is an interactive problem.
给出一个 n 个点 m 条边的有向无环图(DAG)。你会得到该 DAG 的结构,但不会知道 DAG 中每条边的边权。
在任意一对顶点 s 与 t 之间可能存在多条路径,我们将一条路径的权值定义为该路径上所有边权的乘积。记 f(s, t, c) 表示从 s 到 t 的所有不同路径,在所有边权都乘以 c 情况下的权值之和,对 998244353 取模。
你可以进行至多 999 次询问,每次询问你需要给出参数 s, t, c,交互器会返回 f(s, t, c) 的值。
最后,交互器会给出一个参数 k,你需要确定 f(1, n, k) 的值。
数据范围:1 \leq n \leq 10^3,1 \leq m \leq 5 \times 10^3。
时空限制:3s / 1024MiB。
Alice 和 Bob 正在玩取石子游戏。
有 n 个房间,第 i 个房间中有 k_i (k_i \geq 1) 堆石子。Alice 和 Bob 轮流操作,Alice 先手。
每次操作时,玩家必须在当前房间中,选择任意一个非空的堆,然后在该堆中取出任意一个石子。只有在当前房间中将所有石子取完,Alice 和 Bob 才可以到下一个房间继续进行游戏。若某位玩家无法进行操作(即到了最后一个房间并且房间为空),则该玩家输掉游戏。
在游戏开始前,Alice 可以决定房间的访问顺序,访问顺序可以用一个排列 p 描述,表示依次经过房间 p_1, p_2, \dots, p_n,只有房间 p_i 没有石子的情况下,才可以去房间 p_{i + 1}。
假设 Alice 和 Bob 进行的都是最优决策,Alice 想知道他有多少种排列 p 可以获胜。答案对 10^9 + 7 取模。
数据范围:1 \leq n \leq 10^6,1 \leq \sum k_i \leq 10^6,石子数量 \in [1, 10^9]。
时空限制:1s / 512MiB。
有 n 座金矿排成一行,每座金矿有一个属性 a_i,表示该金矿一天产出的金币数量。每座金矿都潜伏着一只有属性 b_i 的哥布林,代表该哥布林的贪婪值。
每天夜晚都会发生以下的事件:你将从第 1 座金矿走到第 n 座金矿,初始金币为 0,每走过一座金矿 i,以下两件事情依次发生:
你需要在这里 m 天,每天都会进行以下操作中的一种:
1 x y:令 a_x = y,修改是持久的。2 x y:令 b_x = y,修改是持久的。3 x:版本回到第 x 天。4 k p1 p2 ... pk:有 k 个位于金矿 p_1, p_2, \dots, p_k 的哥布林向你索要金币的方式变为“若你目前拥有 s 金币,它们将要向你索要 \left\lceil \frac{s}{2} \right\rceil 金币”,变化是临时的。你需要求出当晚要交给哥布林多少金币。数据范围:1\leq n, m \leq 2\times 10^5,0 \leq k \leq 2\times 10^5,0 \leq a_i, b_i \leq 10^9。
时空限制:3s / 256MiB。
有 n 种物品,其中第 i 种物品的重量为 w_i,每一种物品的数量都是无限的。
是否能恰好选 n 个物品,使得所选物品的重量之和为 m。
数据范围:1 \leq n \leq 10^5,0 \leq m \leq n^2,0 \leq w_i \leq n。
时空限制:8s / 1024MiB。
This is an interactive problem.
一个机器人在一个无限大的二维平面的第一象限内移动。最初机器人位于坐标 (s_x, s_y)。最初所有单元格都是白色的。
游戏包含了若干次操作,最多 T = 1000 次操作。每次操作都会按照以下顺序发生事件:
你的目标是在 T 次操作之内使机器人爆炸。
数据范围:1 \leq s_x, s_y \leq 20。
时空限制:2s / 1024MiB。
给出一个长度为 n 的数组 a,其中数组中的元素均为 1 \sim m 中的正整数。
你需要找到四个不同的索引 p, q, r, s,使得 \gcd(a_p, a_q) = 1 且 \gcd(a_r, a_s) = 1。
数据范围:4 \leq n \leq 2 \times 10^5,1 \leq m \leq 10^6,1 \leq a_i \leq m。
时空限制:3s / 256MiB。
有 n 个点,第 i 个点的初始坐标为整点 (x_i, y_i)。
接下来有 m 轮移动,每一轮中的所有 n 个点 (x, y) 都需要移动到 (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1) 四个位置的其中一个。
你需要求出有多少种不同的移动点的方式,使得最终 n 个点两两曼哈顿距离小于等于 k。其中 (x_1, y_1), (x_2, y_2) 的曼哈顿距离为 |x_1 - x_2| + |y_1 - y_2|。
数据范围:1 \leq n \leq 50,1 \leq m \leq 10^5,0 \leq k \leq 10,0 \leq |x_i|, |y_i| \leq 10^5。
时空限制:2s / 1024MiB。