CF1153F Serval and Bonus Problem 做题记录

有一段长为 $l$ 的线段，有 $n$ 个区间，左右端点在 $[0,l)$ 间均匀随机（可能不是整数）

求期望被至少 $k$ 段区间覆盖的长度，对 $998244353$ 取膜。

$1\leq k \leq n \leq 2000$，$1\leq l\leq 10^9$。

首先显然问题与值域 $[0,1]$ 是等价的，因为期望是线性的，可以乘上 $l$，并且实数闭区间和开区间是等价的。

设 $f(x)$ 为 $x$ 这个位置被覆盖至少 $k$ 次的概率，那么答案即为 $\int_0^1f(x)dx$。

考虑一个转化，设 $X$ 是一个 $[0,1]$ 中的随机变量，那么 $X$ 被覆盖至少 $k$ 次的概率就是 $\frac{\int_0^1f(x)dx}{1}=\int_0^1f(x)dx$ 即答案。所以问题变成求 $[0,1]$ 中随机一个位置被覆盖至少 $k$ 次的概率。

不难发现，由于是实数，所以我们并不关心 $X$ 和区间端点的具体取值，只关心它们的相对位置。那么把这 $2n+1$ 个位置拉出来，区间左端点看作左括号，区间右端点看作右括号，设 $dp_{i,j,0/1}$ 表示考虑完前 $i$ 个位置，有 $j$ 个左括号未匹配，没放/放 $X$ 的方案数。那么有转移：

$\begin{cases}dp_{i,j,f}\to dp_{i+1,j+1,f}\\j\times dp_{i,j,f}\to dp_{i+1,j-1,f}&j>0\\ dp_{i,j,f}\to dp_{i+1,j,1}&j\ge k,f=0\end{cases}$

$dp_{2n+1,0,1}$ 除掉总的方案数即为要求的 $\int_0^1f(x)dx$，这个东西乘上 $l$ 就是答案。

代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int S=2005,p=998244353;

int n,k,l;
int dp[2][S*2][2],pd[2][S*2];

inline void add(int &x,int y)
{
	x+=y;
	if(x>=p) x-=p;
}

inline int qpow(int x,int y)
{
	int res=1;
	for(;y>0;y>>=1,x=1ll*x*x%p) res=y&1?1ll*res*x%p:res;
	return res;
}

int main()
{
	scanf("%d%d%d",&n,&k,&l);
	dp[0][0][0]=pd[0][0]=1;
	for(int i=0;i<=n*2;i++)
	{
		int u=i&1,v=i+1&1;
		memset(dp[v],0,sizeof(dp[v]));
		memset(pd[v],0,sizeof(pd[v]));
		for(int j=0;j<=i;j++)
		{
			for(int f=0;f<=1;f++)
			{
				if(dp[u][j][f]==0) continue;
				add(dp[v][j+1][f],dp[u][j][f]);
				if(j>0) add(dp[v][j-1][f],1ll*dp[u][j][f]*j%p);
				if(j>=k&&f==0) add(dp[v][j][1],dp[u][j][f]);
			}
			add(pd[v][j+1],pd[u][j]);
			if(j>0) add(pd[v][j-1],1ll*pd[u][j]*j%p);
		}
	}
	// printf("%d / %d\n",dp[n*2+1&1][0][1],1ll*pd[n*2&1][0]*(n*2+1)%p);
	printf("%d\n",1ll*dp[n*2+1&1][0][1]*qpow(1ll*pd[n*2&1][0]*(n*2+1)%p,p-2)%p*l%p);
	return 0;
}