ZJOI2012 波浪

Link

题意

求长度为$n$的排列,$\sum_{i=2}^{n}|a_i – a_{i-1}|\geq m$的概率。

数据范围$n \leq 50$,最多输出30位小数。

题解

应该是个经典套路题,类似同色不相邻方案计数。

题目要统计概率,其实可以统计方案数然后除$P(n)$。

因为abs有点麻烦可以考虑顺次插入每个数。

$f[i][j][k][0/1/2]$表示现在插入的数为$i$,此时序列的答案为$j$,序列分为了$k$段数的概率,确定了$0/1/2$个端点的方案数。

这里的段并没有赋予每个元素实际上的位置,只是说段与段没有连在一起,终于两个段之间相间隔了几个元素在合法的范围内任意的,所以可以得到如下的转移。

(一)如果这个数新开了一段(和之前的段不相邻),此时对答案的贡献为$-2i$,有$k+1$个位置可供选择。
$$
f[i][j-2i][k+1][0]\leftarrow f[i-1][j][k][0]\times (k+1)
$$
(二)如果这个数把两个相邻的段链接在了一起,对答案的贡献为$2i​$,有$k-1​$个位置可选。
$$
f[i][j+2i][k-1][0]\leftarrow f[i-1][j][k][0]\times (k-1)
$$
(三)如果这个数接在某个段的旁边,对答案的贡献为0,有$2k$个位置可选。
$$
f[i][j][k][0]\leftarrow f[i-1][j][k][0]\times (2k)
$$
(四)如果这个数在边界,而且链接了最靠近边界的那一段,对答案的贡献为$i$,有两个位置可选。
$$
f[i][j+i][k-1][1]\leftarrow f[i-1][j][k][0]\times 2
$$
(五)如果这个数在边界,没有链接两段,对答案的贡献为$-i$,有两个位置可选。
$$
f[i][j-i][k+1][1]\leftarrow f[i-1][j][k][0]\times 2
$$
上面只讨论完了$f[i][j][k][0]$的转移。还需要讨论$f[i][j][1/2]$的转移。

转移的方程一样,但是系数略有不同就不再赘述。

对于第一维可以滚动数组优化,第二维的负数可以整体向右平移。

初始状态
$$
f[1][-2][1][0]=1,f[1][-1][1][1]=2,f[1][0][1][2]=1
$$
题目要求的概率为
$$
\frac{\sum_{i=m}^{\lim}f[n][i][1][2]}{n!}
$$

具体实现

这个题的精度高达30位,如果不写高精度可以用__float128实现。

但是由于float128的时间太慢,对于$K\leq 8$可以用double,$K > 8$用float128。

然后空间也不能开太大,要刚刚好,不然128MB就会被卡。

代码

Leave a Reply

Your email address will not be published. Required fields are marked *