CF1842H

传送门

description

见洛谷翻译

solution

考虑分析一下不等式 \(x_i+x_j\leq 1\)。

• 如果 \(x_i,x_j\leq 0.5\)，一定成立；

• 如果 \(x_i,x_j>0.5\)，一定不成立；

• 如果 \(x_i,x_j\) 中一个 \(>0.5\)，一个 \(\leq 0.5\)，不妨设 \(x_i\leq 0.5\)，则要求 \(0.5-x_i\geq x_j-0.5\)。

可以发现，前两种情况比较简单，后一种情况和 \(x_i\) 与 0.5 差的绝对值有关，于是我们不妨把所有数向左平移 0.5，看起来更舒服。原要求变成 \(x_i+x_j\leq 0\)。

一个不难想的做法是枚举有哪些数是 \(\leq 0\) 的，这样就可以把所有不等式转化为 \(|x_i|\leq |x_j|\) 的形式。所有合法的绝对值的大小排列除以 \(2^nn!\) 就是这种情况对答案贡献的概率（因为每种 \(n\) 个数的大小关系是随机的，规定一个数正负号的概率是 \(\frac{1}{2}\)）。但是后面这个部分相当于求一张图的拓扑序数量，没有多项式复杂度的做法，加上前面 \(2^n\) 枚举，复杂度式不能接受的。

我们尝试不去枚举哪些数是 \(\leq 0\) 的。设 \(f_{mask}\) 表示选出点集为 \(mask\) 的合法的绝对值大小关系排列的数量。根据上面的推导，最后乘上系数 \(\dfrac{1}{2^nn!}\) 就是答案。

我们枚举 \(mask\) 中绝对值最大的数 \(x_i\)，如果它能够作为负数存在于排列中，要求不存在有限制 \(x_i+x_j\geq 0\) 的 \(x_j\) 在排列中；作为非负数同理。

对于 \(x_i+x_i\leq 0\) 这类的限制，还要求 \(x_i\leq 0\)，需要特别注意一下。

细节见代码。

code

Submission #230485940 - Codeforces