#P2612. [ZJOI2012] 波浪

    ID: 1620 远端评测题 6000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>动态规划dp2012各省省选浙江组合数学

[ZJOI2012] 波浪

题目描述

阿米巴和小强是好朋友。

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

于是,这对好朋友不可避免地产生了分歧。为了论证自己的观点,小强建立了一个模型。他海面抽象成一个 11NN 的排列 P1NP_{1\ldots N}。定义波动强度等于相邻两项的差的绝对值的和,即:

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

给你一个 NNMM,问:随机一个 1N1\ldots N 的排列,它的波动强度不小于 MM 的概率有多大?

答案请保留小数点后 KK 位输出,四舍五入。

输入格式

第一行包含三个整数 N,MN, MKK,分别表示排列的长度,波动强度,输出位数。

输出格式

第一行包含一个小数点后 KK 位的实数。

3 3 3
0.667

提示

N=3N = 3 的排列有 66 个:123,132,213,231,312,321123, 132, 213, 231, 312, 321;他们的波动强度分别为 2,3,3,3,3,22, 3, 3, 3, 3, 2。所以,波动强度不小于 33 的概率是 46\frac 46,即 0.6670.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%30\% 的数据,N10N \leq 10

对于另外 30%30\% 的数据, K3K \leq 3

对于另外 30%30\% 的数据,K8K \leq 8

对于另外 10%10\% 的数据,N50N \leq 50

对于 100%100\% 的数据,N100K300M2147483647N \leq 100,K \leq 30,0 \leq M \leq 2147483647