「CTS 2019」随机立方体【容斥原理 + 概率与期望】

Time Limit: 12 Sec Memory Limit: 512 MB

Description

有一个 n×m×ln \times m \times l 的立方体,每个格子上都有一个数,如果某个格子上的数比三维坐标至少有一维相同的其他格子上的数都要大的话,我们就称它是极大的。

现在将 1n×m×l1 \sim n \times m \times ln×m×ln \times m \times l 个数等概率随机填入 n×m×ln \times m \times l 个格子,使得每个数均出现一次,求恰有 kk 个极大的数的概率。答案对 998244353998244353 取模。

查看更多

「CTS 2019」氪金手游【容斥原理 + 树形 DP】

Time Limit: 1 Sec Memory Limit: 512 MB

Description

小刘同学最近迷上了一个新游戏,游戏的内容就是不断地抽卡。现在已知:

  • 卡池里总共有 nn 种卡,第 ii 种卡有一个权值 WiW_i。小刘同学不知道 WiW_i 具体的值是什么,但是 WiW_i 服从一个分布。
  • 具体地,对每个 ii 有三个参数 pi,1,pi,2,pi,3p_{i, 1}, p_{i, 2}, p_{i, 3}WiW_i 将会以 pi,jp_{i, j} 的概率取值为 jj,保证和为 11

小刘每次会氪一元钱来抽一张卡,其中抽到卡 ii 的概率为:

WijWj\frac{W_i}{\sum_j W_j}

小刘会不停地抽卡,直到他手里集齐了全部 nn 种卡。抽卡结束后,记录下来了第一次得到每张卡的时间 {Ti}\{ T_i \}。有 n1n - 1 个二元组 (ui,vi)(u_i, v_i),对于任意的 ii 都必须满足 Tui<TviT_{u_i} < T_{v_i}

查看更多