ARC113F

来做做zhq他们比赛过的压轴题...

题目描述

给出 $N+1$ 个端点 $X_0,...,X_N$ ,有 $N$ 个人,第 $i$ 个人随机出现在 $[X_{i-1},X_i]$ 内,问人两两最小距离的最大值的期望是什么

$N\leq 20$

考虑连续意义下的期望, $f(z)$ 表示所有人相邻距离大于等于z的概率,那么答案就是 $\int f(z)$ ,是个定积分

那么考虑怎么计算这个固定z意义下的概率,考虑dp

首先每个区间左右端点变为 $[x_i-(i-1)z,x_{i+1}-(i-1)z]$ ,之后我们要选取n个实数满足 $y_1<y_2<...<y_n$

我们再把所有的左右端点按顺序排序,考虑设计这样一个dp

$f_{i,j}$ 表示考虑了前i个变量y的值,现在到了区间 $[j,j+1]$ 这个端点的,然后转移我们考虑枚举一个k,让k个人都在这个范围内,即满足 $y_{i-k}<v_j<y_{i-k+1}...y_{i}\leq v_{j+1}$

对应系数是这k个人单调递增,就是一个 $\frac{1}{k!}$ ,同时要乘上每一个人在这个区间中的概率,就是(区间长度/这个人可行区间长度)

于是我们考虑对于z不固定,一个v相当于一个关于z的多项式 $-az+b$ ,带入不同的z有不同的取值

首先枚举 $n^2$ 种大小关系,就是类似什么v大什么v小

又因为我们转移的系数和区间端点有关,也就不难看出是关于区间的一个多项式,也就是关于z的n次多项式

现在我们先把那个分数的分子提出来提前乘,然后分母搞到最后乘

于是我们就能对于每一个系数直接*对应的人的多项式了!

然后最后我们发现答案是一个 $n^2$ 分段的每一段都是O(n)次的函数

那么我们就把每个段都可以单独积分,就做完了

代码中乘上了LCM保证整除没有分数

#include <cstdio>
#include <cassert>
#include <cstring>
#include <algorithm>

long long gcd(long long a, long long b) {
	return (!b) ? a : gcd(b, a % b);
}
const int P = 998244353;
long long p = 1ll * P * P;
inline int mul(const int &a, const int &b) {
	return 1ll * a * b % P;
}
inline int add(int a, const int &b) {
	a += b;
	return(a >= P) ? a - P : a;
}
inline int sub(int a, const int &b) {
	a -= b;
	return (a < 0) ? a + P : a;
}
int qsm(int a, int b) {
	int ans = 1;
	while(b) {
		if(b & 1)ans = mul(ans, a);
		a = mul(a, a);
		b >>= 1;
	}
	return ans;
}
int n, top, ans;
int invmul[51], inv[52];
long long x[51], L;
long long T[10001];
struct info {
	long long x, D;
	int i;
} num[52];
struct poly {
	int num[51];
} f[51][51];
void mul(poly &a, poly b, poly c) {
	for(int i = 0; i <= n; ++i) {
		long long x = 0;
		for(int j = 0; j <= 1 && j <= i; ++j)
			if((x += 1ll * c.num[j] * b.num[i - j]) >= p)x -= p;
		a.num[i] = x % P;
	}
}
bool good[42];
bool cmp(info a, info b) {
	return a.D < b.D || (a.D == b.D && a.i > b.i);
}
void solve(long long L, long long R) {
	for(int i = 0; i < n; ++i) {
		num[i] = (info) {
			x[i], x[i] - 1ll * i *L, i
		}; num[i + n] = (info) {
			x[i + 1], x[i + 1] - 1ll * i *L, i
		};
	}
	std::sort(num, num + (n << 1), cmp);
	memset(f, 0, sizeof f);
	f[0][0].num[0] = 1;
	for(int i = 1; i < (n << 1); ++i) {
		good[num[i - 1].i + 1] ^= 1;
		poly r;
		memset(&r, 0, sizeof r);
		r.num[0] = sub(num[i].x % P, num[i - 1].x % P);//分子
		r.num[1] = sub(num[i - 1].i, num[i].i);
		// printf("%d %d %d %d\n", r.num[0], r.num[1], num[i].x, num[i - 1].x);
		for(int j = 0; j <= n; ++j) {
			for(int k = j; k <= n; ++k) {
				for(int l = 0; l <= n; ++l)
					f[i][k].num[l] = add(f[i][k].num[l], mul(f[i - 1][j].num[l], invmul[k - j]));//逆元
				mul(f[i - 1][j], f[i - 1][j], r);
				if(!good[k + 1])break;//这个区间没有这么多人
			}
		}
	}
	for(int i = 0; i <= n; ++i) {
		// printf("%d %d\n", i, f[(n << 1) - 1][n].num[i]);
		ans = add(ans, mul(mul(f[(n << 1) - 1][n].num[i], inv[i + 1]), sub(qsm(R % P, i + 1), qsm(L % P, i + 1))));//积分部分
	}
	good[num[(n << 1) - 1].i + 1] ^= 1;
}
signed main() {
	scanf("%lld", &n);
	invmul[0] = invmul[1] = inv[0] = inv[1] = 1;
	for(int i = 2; i <= n + 1; ++i)inv[i] = mul(P - P / i, inv[P % i]);
	for(int i = 2; i <= n; ++i)invmul[i] = mul(invmul[i - 1], inv[i]);
	int LCM = 1;
	for(int i = 1; i <= n; i++)LCM = 1ll * (LCM / gcd(LCM, i)) * i;
	// printf("%d?\n", LCM);
	for(int i = 0; i <= n; i++)scanf("%lld", x + i), x[i] *= LCM;
	for(int i = 1; i <= n; ++i)
		for(int j = i + 1; j <= n; ++j)
			for(int k = 0; k < 2; ++k)
				for(int l = 0; l < 2; ++l)
					T[++top] = (x[j - k] - x[i - l]) / (j - i);
	std::sort(T + 1, T + top + 1);
	top = std::unique(T + 1, T + top + 1) - T - 1;
	for(int i = 1; i <= top; ++i) {
		// printf("%d %d %d??\n", i, T[i - 1], T[i]);
		solve(T[i - 1], T[i]);
	}
	for(int i = 1; i <= n; ++i)ans = mul(ans, qsm(sub(x[i] % P, x[i - 1] % P), P - 2));//分母
	printf("%lld\n", mul(ans, qsm(LCM % P, P - 2)));//最后除掉
	return 0;
}

夏晓光(loveJY)的博客

Codeforces Global Round 13