ctt 邮寄

Day 0

Day 1

有一个长度为 $n$ 的数组 $a$，一开始全是 $0$，同时给定整数 $m\le n$ 和一个长度为 $n-m+1$ 的权值数组 $b$。接下来做 $c$ 次操作，每次操作以 $\frac{b_i}{\sum b}$ 的概率选中一个 $[1,n-m+1]$ 的整数 $i$，然后把 $a_{i,i+1,\dots,i+m-1}$ 都加 $1$。
问 $c$ 次操作后 $\sum a_i$ 的期望。
$n,m\le 50, c\lt 998244353, \bmod=998244353$。

维护长度为 $n$ 的数组 $a$ 和 $b$。定义 $i,j$ 匹配当且仅当 $b_i=0$ 且 $b_j=1$。定义一组匹配是一个匹配的集合，满足所有匹配的二元组中的数互不相同。
$m$ 次操作，每次操作修改一个位置。
在初始时，和每次操作之后，回答以下问题：

• 找到一组匹配，使得形如 $(i,j),a_i=a_j$ 的匹配数量最大。
• 在满足以上条件的情况下，使得这组匹配的大小最大。
• 输出这组匹配的大小。

$n,m\le 2\times 10^5, 1\le a_i\le n, 0\le b_i\le 1$。

交互题。有一条不与 $y$ 轴平行的未知直线和一个给定的值域 $V$，满足其不经过 $x,y\in [0,V]$ 的所有整点 $(x,y)$，且直线与 $x=0$ 和 $x=V$ 的交点纵坐标也在 $(0,V)$ 内。
这条直线把值域内所有点划分为两部分，你需要在 $lim$ 次询问内找到一条直线，满足这条直线划分出的集合与未知直线划分的一致。以 $y=kx+b$ 的形式输出，其中 $k,b$ 用分数形式 $\frac{p}{q}$ 表达，要求 $p$ 在 long long 范围内，$q$ 在 int 范围内。
$T\le 1000$。当 $lim=100$ 时 $V\le 10^5$，当 $lim=180$ 时 $V\le 10^9$。

Day 2

交互题。有一个未知的 $n$ 个点竞赛图，每次询问可以知道两点之间的边的方向。
$n\le 300$。你需要在 $T=300$ 组数据下，以平均 $Q=700$ 次以内的询问正确给出一个结点 $u$，其满足：

• 从 $u$ 出发可以到达所有其余结点，并且它到其余点的最短路距离的 $\text{max}$ 最小。

对于两棵 $n$ 个点的有标号树 $T_0,T_1$，我们称 $T_0$ 偏序 $T_1$，当且仅当它们满足如下条件：

• 记 $T$ 是一棵 $n$ 个点的树，$V$ 是它的一个点集，定义 $f(V,T)$ 表示 $V$ 对 $T$ 的导出子图中，度数 $\le 1$ 的点的数量。
• 条件：$\forall S\subset \{1,2\dots,n\}, \exist S\subset T\subset \{1,2,\dots,n\}$ 使得 $f(T,T_0)\le f(S,T_1)$。

定义树 $T_0,T_1$ 属于同一个等价类，当且仅当 $T_0$ 偏序 $T_1$，且 $T_1$ 偏序 $T_0$。
给定 $k$ 棵 $n$ 个点的树，你需要解决两种问题：
问题 $1$：对于被所有这 $k$ 棵树偏序的树，计数它们形成的等价类数量。
问题 $2$：对于偏序所有这 $k$ 棵树的树，计数树的数量。
$n\le 5000, k\le 1000, \bmod=998244353$

给定一棵 $n$ 个点的随机生成的树。
称长为 $n$ 的排列 $P$ 是它的一个拓扑序，当且仅当对于任意 $i=1,2,\dots,n-1$，都存在恰好一个 $j\gt i$ 满足 $P_i,P_j$ 之间有连边。
你需要输出这棵树的 $k$ 个拓扑序，满足：同时存在这些拓扑序的树只有给定的树，且 $k$ 最小。
有 $T$ 组数据。
子任务 $1$：$T=10, n=10$。
子任务 $2$：$T=100, n=100$。

Day 3

有 $n$ 个人，标号为 $i$ 的人实力值为 $i$，他们排成一个环。
每个人有一个归属的队伍，红队或者蓝队。每相邻两个队伍不同的人会进行比赛，实力值高的获胜。
如果蓝队获胜，蓝队加 $1$ 分。
如果红队获胜，并且这个获胜的人排在蓝队的逆时针方向，红队加 $1$ 分。
最后对于每个 $i=-n,-(n-1),\dots,-1,0,1.\dots,n-1,n$，询问当红队比蓝队多 $k$ 分时，有多少种可能的圆排列。
$3\le n\le 3000, \bmod=998244353$

有一段大小为 $m$ 的一维空间，有 $n$ 个有长度的一维物体，第 $i$ 个为 $a_i$。
对于 $i=1,2,\dots,n$，依次执行以下操作：

• 如果还存在一段长度为 $a_i$ 的空间，未放置任何一个物体，则必须选择一个位置（不一定在整点上）把第 $i$ 个物体放入。
• 否则什么也不做。

问有多少种“放进去的物体的总长度”，依次输出。
$n\le 14, m\le 10^{16}$。

交互题。有一棵未知的 $n$ 个点无根树，和一个初始为空的点集 $S$。
你可以进行一些操作，每次操作可以向 $S$ 中加入或者删除一个点，交互库会返回 $S$ 形成的导出子图中，最大的连通块的大小（点数）。
在 $Q=6\times 10^5$ 次操作内，确定这棵树。
$n\le 10000$。