题目描述

「Codechef SEAARC」Sereja and Arcs

数轴上有 $n$ 个点，坐标为 $1, 2, \cdots n$。每个点有个颜色，颜色相同的点两两之间会连一条与经过数轴上方的半圆形圆弧，颜色和端点一样。问共有多少对不同色圆弧相交，答案对大素数取模。

数据范围：$n \le 10^5$。

C. Sakurada Reset

「Gym 102361C」Sakurada Reset（动态规划）

题目描述

给定数列 $A, B$，将数列中的每个子序列都看作一个 $1000$ 进制数，问有多少对 $(x, y)$ 满足 $x$ 是 $A$ 的某个子序列，$y$ 是 $B$ 的某个子序列，并且 $x > y$。本质相同的子序列只算一次，答案对大素数取模。

数据范围：$n, m \le 5000, 1 \le A_i, B_i \le 100$。

定义

对于一张有向图，确定一个根，如果根到 $x$ 的每条路径都经过 $y$，那么称 $y$ 是 $x$ 的支配点。求出原图的一个 dfs 树，那么 $x$ 的支配点一定在 $x$ 到根的链上。如果每个点向自己深度最大的支配点（记作 $\text{idom}(u)$）连边，就构成了支配树。

题目大意

「ARC 096E」Everything On It

求有多少个子集族，满足：

• 其中的每个子集都是 $[n]$ 的一个子集；
• 任意两个子集互不相同；
• $1, 2, \cdots, n$ 都在其中出现了至少两次。

答案对素数 $m$ 取模。

数据范围：$n \le 3000, 10^8 \le m \le 10^9 + 9$。

题目大意

「Codeforces 1043F」Make It One

有 $n$ 个数 $a_1, a_2, \cdots, a_n$。要选出一个子集，使得集合内部的 $\gcd$ 为 $1$，问集合大小的最小值。

数据范围：$n, a_i \le 3 \times 10^5$。

题目大意

「NEERC 2016」Mole Tunnels（BZOJ 4849）

有 $n$ 个洞，$m$ 只鼠，第 $i$ 个洞里有 $c_i$ 份食物。如果 $i > 1$，那么第 $i$ 个洞向 $\lfloor \frac{i}{2} \rfloor$ 个洞连一条无向边。对于每个 $k$，你要为前 $k$ 只鼠制定一个移动方案，使得它们各自移动到某个洞穴后，每个洞穴的鼠的数量不超过该洞中食物的数量（只算前 $k$ 只鼠）。在合法的情况下，要求鼠移动的距离总和最小，你只需输出最小的距离和。

数据范围：$n, m \le 10^5$。

题目大意

「PKUWC 2018」随机游走（LOJ 2542）

给定一棵 $n$ 个结点的树，根为 $r$。有 $Q$ 个询问，每次给定一个点集，问从根开始随机游走，到达这个点集中的所有点的期望步数。

数据范围：$n \le 18, Q \le 5 \times 10^3$。

题目大意

「TJOI 2019」唱、跳、rap 和篮球（Luogu 5339）

共有 $a + b + c + d$ 个人，有 $a$ 个人喜欢唱，有 $b$ 个人喜欢跳，有 $c$ 个人喜欢 rap，有 $d$ 个人喜欢篮球。要求选出 $n$ 个人排队，使得不存在一个位置 $i$，满足位置 $i, i + 1, i + 2, i + 3$ 上的人同时喜欢唱、跳、rap 和篮球。我们称两种方案不同当且仅当有一个位置上的人的爱好不同，求共有多少不同的方案 $\bmod 998244353$ 的结果。

数据范围：$n \le 10^3, a, b, c, d \le 500$。

题目大意

「LOJ 121」动态图连通性

给定一个 $n$ 个点的图和 $m$ 个操作。图一开始是空的，每次操作可以在图中加上一条边，删去一条边或者询问两个点是否连通。你要对于所有询问求出答案。

数据范围：$n \le 5 \times 10^3, m \le 5 \times 10^5$。

题目大意

「LOJ 575」不等关系

给定一个长度为 $n$ 的字符串 $s$，$s_i \in {<, >}$。要求计数长度为 $n + 1$ 的排列 $a$，满足 $a_i < a_{i + 1}$ 当且仅当 $s_i$ 为 $<$，模数为 $998244353$。

数据范围：$n \le 10^5$。