P2612 [ZJOI2012] Waves

Amoeba and Xiaoqiang are good friends. They are watching the waves by the sea. It is Xiaoqiang’s first time facing such surging tides, and he keeps shouting with excitement. Amoeba, however, remains calm, recalling the ups and downs of his career and the setbacks in his relationships... In short, compared with the storms he has experienced, today’s waves are nothing. Thus, a disagreement between the two friends is inevitable. To support his view, Xiaoqiang builds a model. He abstracts the sea surface as a permutation $P_{1 \ldots N}$ of $1$ to $N$. Define the wave intensity as the sum of the absolute differences between adjacent elements, that is: $$L = | P_2 - P_1 | + | P_3 - P_2 | + \ldots + | P_N - P_{N-1} |.$$ Given $N$ and $M$, what is the probability that a uniformly random permutation of $1 \ldots N$ has wave intensity at least $M$? Output the answer rounded to $K$ digits after the decimal point.

The first line contains three integers $N, M$ and $K$, denoting the length of the permutation, the wave intensity threshold, and the number of digits to output, respectively.

Output one real number with exactly $K$ digits after the decimal point.

For $N = 3$, there are $6$ permutations: $123, 132, 213, 231, 312, 321$; their wave intensities are $2, 3, 3, 3, 3, 2$. Therefore, the probability that the wave intensity is at least $3$ is $\frac 46$, i.e., $0.667$. You can also verify this probability with the following code: ```cpp int a[3]={0,1,2},s=0,n=3; for (int i=0;i