CF1153F Serval and Bonus Problem 做题记录

有一段长为 ll 的线段,有 nn 个区间,左右端点在 [0,l)[0,l) 间均匀随机(可能不是整数)

求期望被至少 kk 段区间覆盖的长度,对 998244353998244353 取膜。

1kn20001\leq k \leq n \leq 20001l1091\leq l\leq 10^9

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

f(x)f(x)xx 这个位置被覆盖至少 kk 次的概率,那么答案即为 01f(x)dx\int_0^1f(x)dx

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

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

{dpi,j,fdpi+1,j+1,fj×dpi,j,fdpi+1,j1,fj>0dpi,j,fdpi+1,j,1jk,f=0\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}

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

代码如下:

#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;
}