Codeforces 1295F Good Contest

正文索引 [隐藏]

题目大意

有一个未知的序列 a_1, a_2, \cdots, a_n,每一个数字 a_i 等概率地可能是区间 [l_i, r_i] 内的任意一个整数,试问这个序列单调不递增的概率是多少,答案对 998244353 取模。

数据范围:

  • $2\leq n \leq 50$
  • $0 \leq l_i \leq r_i \leq 998244351$

题目链接:http://codeforces.com/problemset/problem/1295/F

题解

因为序列要保证单调不递增,所以显然状态表示应该类似于 dp[i][v] 表示前 i 个数字保证单调不递增且最后一个数字是 v 的概率。

但是这样表示明显超时,因为状态的数量就可以达到 50 \times 998244351 个,超过了时限可以接受的范围。所以我们考虑将上面这个状态表示的粒度变粗,以降低状态的数量。

因为我们并不关心数字具体是多少,只关心数字的相对大小与属于哪些区间 [l, r],故我们可以发现,实际上本质不同的数字仅有 2n 个,而本质相同的若干个数字的相对大小可以使用组合数处理出来。举一个例子,有区间 [1, 8], [2, 6], [4, 10],那么 [1], [2, 3], [4, 5, 6], [7, 8], [9, 10] 本质不同的数字仅有这五种且同一种数字包含于前三个区间的情况相同,再比如,我要在 [2, 3] 中取 3 个单调不增的数字,那么一共有 C_{2 + 3 – 1}^3 种选法。

那么,这道题目的状态表示基本上已经弄清楚了,我们 [0, 998244351] 中的所有整数划分成本质不同的数字区间 s_1, s_2, \cdots, s_k,然后用 dp[i][s][j] 表示前 i 个数字满足单调不降且后缀的 j 个数字都落在区间 s 中的概率。

当前在 dp[i][s1][j] 状态,考虑 i+1 可选区间内本质不同的数字区间 s2

  • 如果 s1 = s2,即在前一个状态最后一段数字中再多加一个落入 s1
    dp[i + 1][s2][j + 1] += dp[i][s1][j] \div \frac{C_{|s1|+j-1}^j}{|s1|^j} \times \frac{C_{|s1|+j}^{j+1}}{|s1|^{j+1}} \times \frac{|s1|}{r_{i+1}-l_{i+1}+1}
  • 如果 s1 > s2,即在序列后增加一段 s2 仅第 i 个数字落入其中。
    dp[i + 1][s2][j + 1] += dp[i][s1][j] \times \frac{|s2|}{r_{i+1}-l_{i+1}+1}

其中,|s2|,|s1|是求数字区间的大小,\frac{|s2|}{r_{i+1}-l_{i+1}+1} 是计算第 i 个数字选择在数字区间 s2 中的概率,\frac{C_{|s1|+j-1}^j}{|s1|^j} 是在 s1 数字区间中选择 j 个单调不减的数字的方案数。

代码