【CodeForces-1295F】Good Contest • TonyYin's Blog

题意#

数列 $a$ 在下列条件下随机生成。

$a_i$ 是给定的区间 $[l_i, r_i]$ 内的正整数，等概率随机。

求 $a_{1\cdots n}$ 单调不增的概率，对 $998244353$ 取模。

$2\leq n\leq 50$ ， $0\leq l_i, r_i\leq 998244351$ .

分析#

首先容易想到，概率可以由总方案数和单调不增的方案数求得，其中总方案数为：

A=\prod_{i=1}^n (r_i-l_i+1)

只需求出单调不增的序列个数 $B$ ，则：

p=\frac{B}{A}\bmod 998244353

对于值域较小的情况，可以想到设 $f_{i,j}$ 表示：选好了前 $i$ 个数且 $a_i=j$ 的情况下的方案数。

转移只需：

f_{i,j}=\sum_{k\geq j} f_{i-1, k}

但可惜本题中值域较大，考虑做优化。

想到离散化。

对区间端点进行离散化，用 $p_i$ 表示所有端点坐标中数值第 $i$ 大的数，

$a_i$ 表示左端点离散化后编号， $b_i$ 表示右端点离散化后编号。

此时需要微调DP状态，但思路类似。

设 $f_{i, j}$ 表示选好了前 $i$ 个数且 $a_i\in [p_j, p_{j+1}-1]$ ，所形成单调不增数列的方案数。

转移时，由于进行了离散化，我们无法通过枚举确定 $a_{i-1}$ 与 $a_i$ 的大小关系。

退而求其次，再枚举 $k$ ，保证 $a_{k+1},\cdots,a_i$ 的值都在 $[p_j, p_{j+1}-1]$ 内，计算这个长度为 $k$ 的区间内的方案数。

记可能的取值个数 $L = p_{j+1}-p_j$ .

需要在其中选 $i-k$ 个数单调不增，方案数为：

C_{i-k}=\binom{L+i-k-1}{i-k}

这个组合数直接递推预处理就好了：

C_x=\binom{L+x-1}{x} \left\{\begin{array}{lr} L, &x=1 \\ C_{x-1}\cdot (L+x-1)\cdot \operatorname{Inv}(x), &x>1 \end{array}\right.

转移时，倒序枚举所有合法的 $k$ ，具体地：

f_{i,j}=\sum_{j\in [a_k, b_k]\wedge k < i}(f_{k, j+1}\cdot C_{i-k})

每个 $i$ 转移完之后，需要做前缀和，

f_{i,j}=\sum_{k\geq j} f_{i, k}

这样对下一次转移才是对的。

最终 $B=f_{n, 1}$ ，答案为：

\operatorname{Ans}=\frac{B}{A} \bmod 998244353

代码#

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int MAXN = 60, mod = 998244353;
inline int power(int x, int k) {
	int ret = 1;
	while(k) {
		if(k & 1) ret = ret * x % mod;
		x = x * x % mod;
		k >>= 1;
	}
	return ret;
}

int n, l[MAXN], r[MAXN], p[MAXN << 1], N;
int f[MAXN][MAXN << 1], C[MAXN];
signed main() {
	cin >> n;
	for(int i = 1; i <= n; i++) {
		cin >> l[i] >> r[i];
		p[++N] = l[i], p[++N] = ++r[i];
	}
	sort(p + 1, p + N + 1);
	N = unique(p + 1, p + N + 1) - p - 1;
	for(int i = 1; i <= n; i++) {
		l[i] = lower_bound(p + 1, p + N + 1, l[i]) - p;
		r[i] = lower_bound(p + 1, p + N + 1, r[i]) - p;
	}
	l[0] = 1, r[0] = N + 1;
	for(int i = 1; i <= N; i++) f[0][i] = 1;
	for(int i = 1; i <= n; i++) {
		for(int j = l[i]; j < r[i]; j++) {
			int len = p[j + 1] - p[j];
			C[1] = len;
			for(int k = 2; k <= i; k++) 
                C[k] = C[k - 1] * (len + k - 1) % mod * power(k, mod - 2) % mod;
			for(int k = i - 1; k >= 0; k--) {
				(f[i][j] += f[k][j + 1] * C[i - k] % mod) %= mod;
				if(j < l[k] || j >= r[k]) break;
			}
		}
		for(int j = N - 1; j > 0; j--) (f[i][j] += f[i][j + 1]) %= mod;
	}
	int ans = f[n][1];
	for(int i = 1; i <= n; i++)
		ans = ans * power(p[r[i]] - p[l[i]], mod - 2) % mod;
	cout << ans << endl;
	return 0;
}

cpp