题目大意：

传送门

长度为 n n n 的数列，第 i i i 个数可能的值为 [ l i , r i ] [l_i,r_i] [li​,ri​]，求数列为不严格单调递减数列的期望。 （ 2 ≤ n ≤ 50 , 0 ≤ l i ≤ r i ≤ 1 e 9 ） （2\leq n \leq 50,0 \leq l_i \leq r_i \leq 1e9） （2≤n≤50,0≤li​≤ri​≤1e9）

Solution:

我们把这些区间分割成两两之间不互相覆盖的若干块，把这些分割后的区间从左到右标上号，可以得到如下结论：对于任意两个数 i < j i \lt j i<j， i i i 所属的区间编号一定大于等于 j j j 所属的区间编号，因此我们可以想到一种 dp 的状态： d p [ i ] [ j ] dp[i][j] dp[i][j] 表示前 i i i 个数，第 i i i 个数在第 j j j 个区间的合法方案数，转移时枚举第 j j j 个区间能加多少个数 k k k ，转移方程为 d p [ i ] [ j ] + = d p [ i − k ] [ j + 1 ∼ c n t ] ∗ C l e n + k − 1 l e n − 1 dp[i][j]+=dp[i-k][j+1\sim cnt]*C_{len+k-1}^{len-1} dp[i][j]+=dp[i−k][j+1∼cnt]∗Clen+k−1len−1​， l e n len len指的是第 j j j 个区间的长度， c n t cnt cnt 指的是总区间个数，最后答案就是 ∑ i = 1 c n t d p [ n ] [ i ] ∏ i = 1 n ( r i − l i + 1 ) \frac {\sum_{i=1}^{cnt}dp[n][i]}{\prod_{i=1}^n(r_i-l_i+1)} ∏i=1n​(ri​−li​+1)∑i=1cnt​dp[n][i]​

代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int mod=998244353;
int n;
int l[55],r[55],lsh[110],cnt;
int dp[55][110],sum;
int fast_pow(int a,int x)
{
	int ans=1;
	for (;x;x>>=1,a=1ll*a*a%mod)
		if (x&1) ans=1ll*ans*a%mod;
	return ans;
}
int C(int x,int y)
{
	int ans=1;
	for (int i=1;i<=x;i++)
		ans=1ll*ans*(y+1-i)%mod*fast_pow(i,mod-2)%mod;
	return ans;
}
int main()
{
	scanf("%d",&n);sum=1;
	for (int i=1;i<=n;i++)
	{
		scanf("%d%d",&l[i],&r[i]);
		r[i]++;lsh[++cnt]=l[i];lsh[++cnt]=r[i];
		sum=1ll*sum*(r[i]-l[i])%mod;
	}
	sort(lsh+1,lsh+1+cnt);
	cnt=unique(lsh+1,lsh+1+cnt)-lsh-1;
	for (int i=1;i<=n;i++) l[i]=lower_bound(lsh+1,lsh+1+cnt,l[i])-lsh;
	for (int i=1;i<=n;i++) r[i]=lower_bound(lsh+1,lsh+1+cnt,r[i])-lsh;
	for (int i=1;i<=cnt;i++) dp[0][i]=1;
	for (int i=1;i<=n;i++)
	{	
		for (int j=l[i];j<r[i];j++)
		{
			for (int k=i;k>0;k--)
			{
				if (j<l[k]||j>=r[k]) break;
				dp[i][j]=(dp[i][j]+1ll*dp[k-1][j+1]*C(i-k+1,i-k+lsh[j+1]-lsh[j]))%mod;
			}
		}
		for (int j=cnt-1;j>=1;j--)
		{
			dp[i][j]+=dp[i][j+1];if (dp[i][j]>=mod) dp[i][j]-=mod;
		}
	}
	printf("%d",1ll*dp[n][1]*fast_pow(sum,mod-2)%mod);
}