Comet OJ

C0834 [ZJOI2012]波浪

内存限制：256 MB 时间限制：10000 ms

题目描述

阿米巴和小强是好朋友。

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

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

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

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

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

输入格式

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

输出

输出包含一个小数点后 $K$ 位的实数。

样例

样例输入 1

3 3 3

样例输出 1

0.667

提示

【样例说明】

$N = 3$ 的排列有 $6$ 个：123，132，213，231，312，321；他们的波动强度分别为 2，3，3，3，3，2。所以，波动强度不小于 $3$ 的概率是 $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);

【数据规模】

对于 30% 的数据，$N ≤ 10$。

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

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

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

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