题目链接：[CTS2019] 氪金手游

题意：

给定一棵 $n$ 个节点的树，每条边定向。每个节点有一个权值 $w_i\in\{1,2,3\}$，$w_i=j$ 的概率为 $p_{i,j}$。

第 $i$ 个点在卡池中放 $w_i$ 个，每次等概率从卡池中取出一个点。求 $n$ 个点被首次抽出的顺序，满足树上边的方向的概率。

$1\le n\le 10^3$

- 阅读剩余部分 -

题目链接：[AGC028E] High Elements

题意：

你有一个 $1,2,\cdots,n$ 的排列 $P$。设一个长度为 $n$ 的 $01$ 字符串 $S$ 合法，当且仅当，先设两个空序列 $A,B$，我们按照 $1$ 到 $n$ 的顺序，若 $S$ 当前位为 $1$ 则把当前位的 $P$ 添加到序列 $A$ 的末尾，否则添加到序列 $B$ 的末尾，使得 $A,B$ 的前缀最大值个数相等。求字典序最小的合法字符串 $S$。

$1\le n\le 2\times 10^5$

- 阅读剩余部分 -

题目链接：[CTS2019] 珍珠

题意：

有 $n$ 个在范围 $[1,D]$ 内的整数均匀随机变量。

求至少能选出 $m$ 个瓶子，使得存在一种方案，选择一些变量，并把选出来的每一个变量放到一个瓶子中，满足每个瓶子都恰好装两个值相同的变量的概率。

$1\le D\le 10^5, 1\le n\le 10^9, 0\le m\le 10^9$。

- 阅读剩余部分 -

题目链接：[CTS2019] 随机立方体

题意：

有一个 $n\times m\times l$ 的立方体，立方体中每个格子上都有一个数，如果某个格子上的数比三维坐标至少有一维相同的其他格子上的数都要大的话，我们就称它是极大的。
现在将 $1\sim n\times m\times l$ 这 $n\times m\times l$ 个数等概率随机填入 $n\times m\times l$ 个格子（即任意数字出现在任意格子上的概率均相等），使得每个数恰出现一次，求恰有 $k$ 个极大的数的概率。
$1\le T\le 10, 1\le n\le 5\times 10^6$。

- 阅读剩余部分 -

题目链接：[USACO18DEC] Balance Beam P

题意：

给定长度为 $n$ 的序列 $\{a_n\}$，初始有一个棋子在位置 $i$。每一轮可以选择结束游戏，获得当前所在节点的分数 $a_i$，也可以选择继续游戏，则棋子等概率移至 $i-1,i+1$，若走出序列则游戏结束，分数为 $0$。
对于 $i\in[1,n]$，求出初始棋子在 $i$，能得到的最大期望分数。
$1\le n\le 10^5$。

- 阅读剩余部分 -