「Codeforces Round #551」F. Serval and Bonus Problem

Posted on | Edited on | In , ,

Problem

Description

给定一条长度为 l 的线段 s ，在 s 上通过等概率随机选择两个端点的方式生成 n 条线段（端点坐标可以是实数）。
求 s 上被至少 k 条随机生成的线段覆盖的长度的期望。

Constraints

1 \le k \le n \le 2000, 1 \le l \le 10^{9}

Solution

Analysis

首先显然可以把 s 的长度看成 1 ，最后把答案乘上 l 就行了。
容易知道 [0, 1] 上的点 x 被一条随机线段覆盖（即两个端点分属两侧）的概率为 P(x) = 1 - x^{2} - (1 - x)^{2} = 2x(1 - x) 。
那么点 x 被至少 k 条随机线段覆盖的概率 f_{k}(x) 即为：

\begin{aligned} f_{k}(x) &= \sum_{i = k}^{n} \binom{n}{i} P^{i}(x) (1 - P(x))^{n - i} \\ &= \sum_{i = k}^{n} \binom{n}{i} (2x(1 - x))^{i} \sum_{j = 0}^{n - i} \binom{n - i}{j} (-2x(1 - x))^{j} \\ &= \sum_{i = k}^{n} \binom{n}{i} \sum_{j = 0}^{n - i} \binom{n - i}{j}(-1)^{j} (2x(1 - x))^{i + j} \end{aligned}

答案即为 f_{k}(x) 在 [0, 1] 上的定积分：

\begin{aligned} \int_{0}^{1} f_{k}(x) \mathrm{d} x &= \int_{0}^{1} \left( \sum_{i = k}^{n} \binom{n}{i} \sum_{j = 0}^{n - i} \binom{n - i}{j}(-1)^{j} (2x(1 - x))^{i + j} \right) \mathrm{d} x \\ &= \sum_{i = k}^{n} \binom{n}{i} \sum_{j = 0}^{n - i} \binom{n - i}{j}(-1)^{j} 2^{i + j} \int_{0}^{1} x^{i + j} (1 - x)^{i + j} \mathrm{d} x \end{aligned}

此处式子最后的积分是 Beta Function 的形式，则有：

B(n, m) = \int_{0}^{1} x^{n - 1} (1 - x)^{m - 1} \mathrm{d} x = \frac{\Gamma(n) \Gamma(m)}{\Gamma(n + m)}

而众所周知对于正整数 n ，有 \Gamma(n) = (n - 1)! 。则：

\int_{0}^{1} x^{i + j} (1 - x)^{i + j} \mathrm{d} x = B(i + j + 1, i + j + 1) = \frac{\Gamma(i + j + 1)^{2}}{\Gamma(2(i + j + 1))} = \frac{(i + j)!^{2}}{(2i + 2j + 1)!}

于是有：

\begin{aligned} \int_{0}^{1} f_{k}(x) \mathrm{d} x &= \sum_{i = k}^{n} \binom{n}{i} \sum_{j = 0}^{n - i} \binom{n - i}{j}(-1)^{j} 2^{i + j} \frac{(i + j)!^{2}}{(2i + 2j + 1)!} \\ &= n! \sum_{i = k}^{n} \frac{1}{i!} \sum_{j = 0}^{n - i} \frac{(-1)^{j}}{j!} \frac{2^{i + j} (i + j)!^{2}}{(n - i - j )! (2i + 2j + 1)!} \\ &= n! \sum_{i = k}^{n} \frac{2^{i} i!^{2}}{(n - i)! (2i + 1)!} \sum_{j = k}^{i} \frac{1}{j!} \frac{(-1)^{i - j}}{(i - j)!} \end{aligned}

后一个 \sum 卷积处理即可。

时间复杂度 O(n \log{n}) 。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include <cstdio>
#include <algorithm>

using i64 = long long;

constexpr int maxn = 4096;

constexpr int mod = 998244353;
constexpr int primitive_root = 3;

inline int sub(const int &x, const int &y) {
	return x < y ? x - y + mod : (x - y);
}
inline void inc(int &x, const int &y) {
	x += y; (mod <= x) and (x -= mod);
}

template <class _Tp>
inline int fpow(_Tp x, int n) {
	int pw = 1;
	for (; n; n >>= 1, x = (i64)x * x % mod)
		if (n & 1) pw = (i64)pw * x % mod;
	return pw;
}

template <class _Tp>
inline void swap(_Tp &x, _Tp &y) {
	_Tp z = x; x = y; y = z;
}

inline int sqr(const int &x) {
	return (i64)x * x % mod;
}

namespace poly {

constexpr int maxn = 4096;

using poly_t = int[maxn];
using poly = int *const;

inline int calcpw2(const int &n) {
	for (int pw = 1; ; pw <<= 1)
		if (n < pw) return pw;
}

poly_t wn, iwn;

inline void init() {
	const int unit_root = fpow(primitive_root, (mod - 1) / maxn);
	wn[0] = iwn[0] = 1;
	for (int i = 1; i < maxn; ++i)
		wn[i] = (i64)wn[i - 1] * unit_root % mod;
	std::reverse_copy(wn + 1, wn + maxn, iwn + 1);
}

void DFT(poly &a, const int &n, const poly &omega = wn) {
	static poly_t curw; curw[0] = 1;

	for (int i = 0, j = 0; i < n; ++i) {
		if (i < j) swap(a[i], a[j]);
		for (int l = n >> 1; (j xor_eq l) < l; l >>= 1);
	}

	poly endpos = a + n, wendpos = omega + maxn;
	for (int l = 1, tp = maxn >> 1; l < n; l <<= 1, tp >>= 1) {
		for (int *i = curw, *w = omega + tp; w < wendpos; w += tp)
			*++i = *w;
		for (int *i = a, z; i < endpos; i += l + l)
			for (int j = 0; j < l; ++j)
				z = (i64)i[j + l] * curw[j] % mod,
				i[j + l] = sub(i[j], z),
				inc(i[j], z);
	}
}

void IDFT(poly &a, const int &n) {
	DFT(a, n, iwn);
	const int invn = fpow(n, mod - 2);
	for (int i = 0; i < n; ++i)
		a[i] = (i64)a[i] * invn % mod;
}

}

inline int io() {
	static int v;
	return scanf("%d", &v), v;
}

int fac[maxn], ifac[maxn];

inline void init(const int &n) {
	fac[0] = fac[1] = 1;
	for (int i = 2; i <= n; ++i)
		fac[i] = (i64)fac[i - 1] * i % mod;
	ifac[n] = fpow(fac[n], mod - 2);
	for (int i = n; i; --i)
		ifac[i - 1] = (i64)ifac[i] * i % mod;
}

int main() {
	const int n = io(), k = io(), l = io();
	init(n + n + 1); poly::init();

	static poly::poly_t f, g;

	std::copy(ifac + k, ifac + n + 1, f + k);
	std::copy(ifac, ifac + n + 1, g);
	for (int i = 1; i <= n; i += 2)
		g[i] = mod - g[i];

	const int N = poly::calcpw2(n + n);
	poly::DFT(f, N); poly::DFT(g, N);
	for (int i = 0; i < N; ++i)
		f[i] = (i64)f[i] * g[i] % mod;
	poly::IDFT(f, N);

	i64 ans = 0;
	for (int i = k, pw2 = fpow(2, k); i <= n; ++i, inc(pw2, pw2))
		ans += (i64)f[i] * pw2 % mod * sqr(fac[i]) % mod * ifac[n - i] % mod * ifac[i + i + 1] % mod;
	printf("%lld\n", ans % mod * fac[n] % mod * l % mod);

	return 0;
}