题目描述
阿米巴和小强是好朋友。
阿米巴和小强在大海旁边看海水的波涛。小强第一次面对如此汹涌的海潮,他兴奋地叫个不停。而阿米巴则很淡定,他回想起曾经的那些日子,事业的起伏,情感的挫折……总之今天的风浪和曾经经历的那些风雨比起来,简直什么都不算。
于是,这对好朋友不可避免地产生了分歧。为了论证自己的观点,小强建立了一个模型。他海面抽象成一个 $1$ 到 $N$ 的排列 $P_{1\ldots N}$。定义波动强度等于相邻两项的差的绝对值的和,即:
$$ L = | P_2 – P_1 | + | P_3 – P_2 | +\ldots + | P_N – P_{N-1} | $$
给你一个 $N$ 和 $M$,问:随机一个 $1\ldots N$ 的排列,它的波动强度不小于 $M$ 的概率有多大?
答案请保留小数点后 $K$ 位输出,四舍五入。
输入格式
第一行包含三个整数 $N, M$ 和 $K$,分别表示排列的长度,波动强度,输出位数。
输出格式
第一行包含一个小数点后 $K$ 位的实数。
输入输出样例 #1
输入 #1
1 |
|
输出 #1
1 |
|
说明/提示
$N = 3$ 的排列有 $6$ 个:$123, 132, 213, 231, 312, 321$;他们的波动强度分别为 $2, 3, 3, 3, 3, 2$。所以,波动强度不小于 $3$ 的概率是 $\frac 46$,即 $0.667$。
你也可以通过下面的代码来验证这个概率:
1 |
|
【数据规模】
对于 $100%$ 的数据,$0 \leq M \leq 2147483647$。
请注意本题不存在一个测试点使得 $N,K$ 均达到最大值。
测试点编号 | $N \le$ | $K \leq$ |
---|---|---|
$1 \sim 3$ | $10$ | $30$ |
$4 \sim 6$ | $100$ | $3$ |
$7 \sim 9$ | $100$ | $8$ |
$10$ | $50$ | $30$ |
题解
考虑去掉绝对值来计算序列中每个数的贡献,计算方式举例如下:
- 对于序列 $2, 1, 4$,$1$ 的贡献为 $-2 \times 1$;
- 对于 $2,5,4$,$5$ 的贡献为 $2 \times 5$;
- 对于 $2, 3, 4$,$3$ 的贡献为 $0$。
因此序列 $a,b,c$ 中,$b$ 的贡献为 $(-b\times(\text{sgn}(a-b)+\text{sgn}(c-b)))$。如果 $b$ 的右端没有 $c$,则 $\text{sgn}(c-b) = 0$,左侧同理。
生成排列的方法之一:$n$ 个空位,把 $1$ 到 $n$ 逐个插入到某个空位。插入 $i$ 时只要看它和多少已插入的数相邻。
$f(i,j,k,l)$ 表示已经插入了 $i$ 个点,共 $j$ 段连续,当前总贡献为 $k$,边界共放了 $l$ 个的方案数。考虑到 $k$ 可能为负数,作为数组下标时要加偏移量 $-5000$。
插入 $i$ 分多种情况,其中 $x,y < i$,$_$ 表示一个还未插入的空位,将来会有 $_ > i$:
- 插入在边界,且与一段相连,形如 $x,i$,贡献为 $i$,$j \ne 0$ 时方案数 $2-l$;
- 插入在边界,自成一段,形如 $_,i$,贡献为 $-i$,方案数 $2-l$;
- 插入不在边界,与一段相连,形如 $x,i,_$,贡献为 $0$,$j \ne 0$ 时方案数 $2j-l$;
- 插入不在边界,自成一段,形如 $_,i,_$,贡献为 $-2i$,方案数 $j+1-l$;
- 插入不在边界,而且这次插入使得两段相连,形如 $x,i,y$,贡献为 $2i$,$j \ge 2$ 时方案数 $j-1$;
答案显然是
$$
ans = \frac{\sum_{k>0}f(n,1,k,2)}{n!}
$$
$k \le 8$ 用 long double,其余使用 __float128
。