P6295 有标号 DAG 计数

题目描述

阿米巴和小强是好朋友。

阿米巴和小强在大海旁边看海水的波涛。小强第一次面对如此汹涌的海潮，他兴奋地叫个不停。而阿米巴则很淡定，他回想起曾经的那些日子，事业的起伏，情感的挫折……总之今天的风浪和曾经经历的那些风雨比起来，简直什么都不算。

于是，这对好朋友不可避免地产生了分歧。为了论证自己的观点，小强建立了一个模型。他海面抽象成一个 $1$ 到 $N$ 的排列 $P_{1\dots N}$。定义波动强度等于相邻两项的差的绝对值的和，即：

$$L=|P_2–P_1|+|P_3–P_2|+\dots +|P_N–P_{N-1}|$$

给你一个 $N$ 和 $M$，问：随机一个 $1\dots N$ 的排列，它的波动强度不小于 $M$ 的概率有多大？

答案请保留小数点后 $K$ 位输出，四舍五入。

输入格式

第一行包含三个整数 $N,M$ 和 $K$，分别表示排列的长度，波动强度，输出位数。

输出格式

第一行包含一个小数点后 $K$ 位的实数。

输入输出样例 #1

输入 #1

3 3 3

输出 #1

0.667

说明/提示

$N=3$ 的排列有 $6$ 个：$123,132,213,231,312,321$；他们的波动强度分别为 $2,3,3,3,3,2$。所以，波动强度不小于 $3$ 的概率是 $\frac{4}{6}$，即 $0.667$。

你也可以通过下面的代码来验证这个概率：

int a[3]={0,1,2},s=0,n=3;
for (int i=0;i<1000000;i++){
    random_shuffle(a,a+n);
    int t=0;
    for (int j=0;j<n-1;j++) t+=abs(a[j+1]-a[j]);
    if (t>=3) s++;
}
printf("%.3f\n",s/1000000.0);

【数据规模】

对于 $100\mathrm{\%}$ 的数据，$0\le M\le 2147483647$。

请注意本题不存在一个测试点使得 $N,K$ 均达到最大值。

测试点编号	$N\le$	$K\le$
$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$，$\mathrm{\_}$ 表示一个还未插入的空位，将来会有 $\mathrm{\_}>i$：

• 插入在边界，且与一段相连，形如 $x,i$，贡献为 $i$，$j\ne 0$ 时方案数 $2-l$；
• 插入在边界，自成一段，形如 $\mathrm{\_},i$，贡献为 $-i$，方案数 $2-l$；
• 插入不在边界，与一段相连，形如 $x,i,\mathrm{\_}$，贡献为 $0$，$j\ne 0$ 时方案数 $2j-l$；
• 插入不在边界，自成一段，形如 $\mathrm{\_},i,\mathrm{\_}$，贡献为 $-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<=8$ 用 long double，其余使用 __float128。