Description

给你三个数\(n,m,q\)。问你一个\(1 \cdots n\)的排列中,两两差值之和大于等于\(m\)的概率是多少,保留\(q\)位小数,\(q \leq 30\)。

Solution

题目里面有个绝对值非常不好做,那么我们考虑怎么把这个绝对值去掉,于是可以从小到大插入所有数

设\(f[i][j][k][l]\)表示插入\(i\)个数,当前序列波动值为\(j\),序列现在被分为\(k\)个连续的段,序列边界的状态为\(l\),\(l\)为\(0\)表示边界没有数,为\(1\)表示边界有一个数,为\(2\)表示边界有两个数。

插入一个数有以下几种情况:

1.插入以后它两边都没有数: \(f[i][j+2*i][k-1][l] += f[i-1][j][k][l]*(k-1)\)

2.插入以后它两边都有数。\( f[i][j-2*i][k+1][l]+=f[i-1][j][k][l]*(k+1-l)\)

3.插入以后它的一边有数。\(f[i][j][k][l]+=f[i-1][j][k][l]*(k*2-l)\)

4.插入在边界上,且它旁边没有数。\(f[i][j+i][k][l+1]+=f[i-1][j][k][l]*(2-l)\)

5.插入在边界上,且它旁边有数。\(f[i][j-i][k+1][l+1]+=f[i-1][j][k][l]*(2-l)\)

转移系数很好考虑,这里就不说了

注意精度问题, __float128double要分类讨论


打赏作者
5+

发表评论

电子邮件地址不会被公开。 必填项已用*标注