夏晓光(loveJY)的博客

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

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

又是连续期望怎么搞啊...

zhq:这个等价于$[0,1)$每个点出现次数大于k的概率求和,就是$f(x)$表示x这个点出现次数大于k的概率,然后$\int f(x)$

这个可以考虑dp啊,计数转期望

首先抽象为相对顺序,干掉所谓的实数坐标

$f_{i,j,k}$表示考虑了i个点,然后现在有j个左端点没有封闭,有k个x被完全覆盖的方案数

那么如果$j\geq k$,就能够直接放入这个点,$f_{i,j,0}$转移到$f_{i+1,j,1}$

否则我们这个点可以逼死一个左端点,$f_{i,j,k}*j->f_{i+1,j-1,k}$

同时可以开一个左端点,就是$f_{i,j,k}->f_{i+1,j+1,k}$

我们要求的就是$f_{2n+1,0,1}$

但是仔细一想直接用这个乘上$\frac{1}{(2n+1)!}$不太对啊,因为这个式子是考虑所有点本质不同的

因此我们再乘$n!$和$2^n$钦定端点不同区间不同即可!

最后$*l$

//让世界计数吧!
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int P = 998244353;
const int MAXN = 4050;
int n, K, l;
inline int add(int x, int y) {
	x += y;
	if(x >= P)x -= P;
	return x;
}

inline ll ksm(ll x, ll y) {
	ll ans = 1;
	while(y) {
		if(y & 1)ans = ans * x % P;
		x = x * x % P;
		y >>= 1;
	}
	return ans;
}

ll fac[MAXN], ifac[MAXN];

inline void init() {
	fac[0] = ifac[0] = 1;
	for(int i = 1; i <= 2 * n + 1; ++i)fac[i] = fac[i - 1] * i % P;
	ifac[2 * n + 1] = ksm(fac[2 * n + 1], P - 2);
	for(int i = 2 * n; i >= 1; --i)ifac[i] = ifac[i + 1] * (i + 1) % P;
}

int f[MAXN][MAXN][2];

int main() {
	scanf("%d%d%d", &n, &K, &l);
	init();
	f[0][0][0] = 1;
	for(int i = 1; i <= 2 * n + 1; ++i) {
		for(int j = 0; j <= i; ++j) {
			for(int k = 0; k <= 1; ++k) {
				f[i][j][k] = add(f[i][j][k], 1ll * (j + 1) * f[i - 1][j + 1][k] % P);
				f[i][j][k] = add(f[i][j][k], f[i - 1][j - 1][k]);
				if(k && j >= K)
					f[i][j][k] = add(f[i][j][k], f[i - 1][j][k ^ 1]);
			}
		}
	}
	printf("%lld\n", 1ll * f[2 * n + 1][0][1] * ksm(2, n) % P * fac[n] % P * ifac[2 * n + 1] % P * l % P);
	return 0;
}