CF1295F - Good Contest

题意：
\(a_i\)​ 是在 \([l_i​,r_i]\) 上均匀随机分布的整数，求 \(a_{1\dots n}\)​ 单调不增的概率。
对 \(998244353\) 取模。
\(2\le n \le 50,0\le l_i\le r_i\le998244351\)。

首先可以把概率转化为总方案数在除以 \(\prod r_i-l_i+1\)，
考虑出朴素的 dp，设 \(f_{i,j}\) 为 $选了前 \(i\) 个且最后一个数为 \(j\)，
转移方程为 \(f_{i,j}=\sum_{k\ge j}f_{i-1,k}\)。
但是时间复杂度 \(O(nV)\)，问题出在值域太大的问题上。
考虑优化状态，把所有区间变成左闭右开然后再离散化，把值域分成了 \(O(n)\) 段，然后再做 dp。
但是同一段的数是无法知道大小关系的，所有 dp 还有枚举连续段，然后通过组合数算出不降的方案数。
通过前缀和优化可做到 \(O(n^3)\)。

const int N = 55;
int n, a[N], b[N], c[N << 1], len;
mint f[N], g[N]; 
void solve() {
	cin >> n;
	FOR(i, 1, n) {
		cin >> a[i] >> b[i];
		b[i]++;
		c[++len] = a[i];
		c[++len] = b[i];
	}
	sort(c + 1, c + len + 1);
	len = unique(c + 1, c + len + 1) - c - 1; 
	FOR(i, 1, n) {
		a[i] = lower_bound(c + 1, c + len + 1, a[i]) - c;
		b[i] = lower_bound(c + 1, c + len + 1, b[i]) - c;
	}
	f[0] = 1;
	ROF(j, len - 1, 1) {
		int l = c[j + 1] - c[j];
		g[0] = 1;
		FOR(i, 1, n) g[i] = g[i - 1] * (l + i - 1) / i;
		ROF(i, n, 1) {
			if(a[i] <= j && j < b[i]) {
				ROF(k, i - 1, 0) {
					f[i] += f[k] * g[i - k];
					if(a[k] > j || j >= b[k]) break;
				}
			}
		}
	}
	mint ans = f[n];
	FOR(i, 1, n) {
		ans /= c[b[i]] - c[a[i]];
	}
	cout << ans << endl;
}