T1

题目描述

阿米巴和小强是好朋友。
阿米巴和小强在大海旁边看海水的波涛。小强第一次面对如此汹涌的海潮，他兴奋地叫个不停。而阿米巴则很淡定，他回想起曾经的那些日子，事业的起伏，情感的挫折……总之今天的风浪和曾经经历的那些风雨比起来，简直什么都不算。
于是，这对好朋友不可避免地产生了分歧。为了论证自己的观点，小强建立了一个模型。他海面抽象成一个 $1$ 到 $N$ 的排列 $P[1…N]$ 。定义波动强度等于相邻两项的差的绝对值的和，即：
$L = | P_2 - P_1 | + | P_3 - P_2 | + \cdots + | P_N - P_{N-1} |$
给你一个 $N$ 和 $M$ ，问：随机一个 $1…N$ 的排列，它的波动强度不小于 $M$ 的概率有多大？

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

【数据规模】对于30%的数据，N ≤ 10。

对于另外30%的数据，K ≤ 3。

对于另外30%的数据，K ≤ 8。

对于另外10%的数据，N ≤ 50。

对于100%的数据，N ≤ 100，K ≤ 30，0 ≤ M ≤ 2147483647。

30分做法

由于K比较小，可以用随机化求概率，如枚举一百万个排列并计算。

正解

~~数学课上，我们学到~~概率= $\frac{可行方案数}{总方案数}$
显然，总方案数为 $n!$
那么，可行方案数怎么求呢？

考虑每个排列对总排列的贡献， $\sum\limits_{i=2}^{n}|P[i] - P[i - 1]|$ 可以拆分成 $\sum\limits_{i=1}^{n}P[i]*a[i]$ , 其中 $a[i]$ 是 $i$ 的贡献, $P[i] = n - i$ ,可以取到 $[-2, 2]$ ，如果不考虑边界的话，只会取到 $-2,\ 0,\ 2$ 这三个数。

从大到小插入数字，用f[i][j][k]表示考虑前i大的数字，这i个数字在最后的排列中是连续的j段，这i个数字对L的贡献为k，的方案数
那么，怎么进行转移呢？
我们可以看出，序列分为不连续的几段
接下来，我们要把 $i+1$ 这个元素（值为n-i）的值插入进去.
有三种情况
第一种， $i+1$ 连接了两个
$e,k,p$ 分别是三种不同的情况: (半圆的直径为1)

$i+1$ 连接两段
$f[i+1][j-1][k-2*(n-i)]$
$i+1$ 另起炉灶
$f[i+1][j+1][k+2*(n-i)]$
$i+1$ 依附于一段
$f[i+1][j][k]$
分别更新即可。
对于这总方法，我们形象地称之为填坑DP

T2

分类讨论
当k = 0时，只有一种：

当k = 1时，只有

两种
当k = 2时，除上面的两种外，还有

三种。
这些都很简单。
但是， $n = 3$ 时就不简单了, 需要使用动态规划解决问题。
第一步，设计状态。
设 $f[i][j][k]$ 为所有只包含前 $i$ 个数，方向为j(需要方向判断，因为“不喜欢”是单向的),
$i, i-1, i-2$ 这三个数的状态为k (这一维大小2^6)