[ZJOI2012]波浪

题目描述

阿米巴和小强是好朋友。 阿米巴和小强在大海旁边看海水的波涛。小强第一次面对如此汹涌的海潮,他兴奋地叫个不停。而阿米巴则很淡定,他回想起曾经的那些日子,事业的起伏,情感的挫折……总之今天的风浪和曾经经历的那些风雨比起来,简直什么都不算。 于是,这对好朋友不可避免地产生了分歧。为了论证自己的观点,小强建立了一个模型。他海面抽象成一个 $1$ 到 $N$ 的排列 $P_{1\ldots N}$。定义波动强度等于相邻两项的差的绝对值的和,即: $$L = | P_2 – P_1 | + | P_3 – P_2 | +\ldots + | P_N – P_{N-1} |$$ 给你一个 $N$ 和 $M$,问:随机一个 $1\ldots 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$ 的概率是 $\frac 46$,即 $0.667$。 你也可以通过下面的代码来验证这个概率: ```cpp 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 \leq 10$。 对于另外 $30\%$ 的数据, $K \leq 3$。 对于另外 $30\%$ 的数据,$K \leq 8$。 对于另外 $10\%$ 的数据,$N \leq 50$。 对于 $100\%$ 的数据,$N \leq 100,K \leq 30,0 \leq M \leq 2147483647$。