有一段长为 的线段,有 个区间,左右端点在 间均匀随机(可能不是整数)
求期望被至少 段区间覆盖的长度,对 取膜。
,。
首先显然问题与值域 是等价的,因为期望是线性的,可以乘上 ,并且实数闭区间和开区间是等价的。
设 为 这个位置被覆盖至少 次的概率,那么答案即为 。
考虑一个转化,设 是一个 中的随机变量,那么 被覆盖至少 次的概率就是 即答案。所以问题变成求 中随机一个位置被覆盖至少 次的概率。
不难发现,由于是实数,所以我们并不关心 和区间端点的具体取值,只关心它们的相对位置。那么把这 个位置拉出来,区间左端点看作左括号,区间右端点看作右括号,设 表示考虑完前 个位置,有 个左括号未匹配,没放/放 的方案数。那么有转移:
除掉总的方案数即为要求的 ,这个东西乘上 就是答案。
代码如下:
#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;
}