Description

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.

Input Format

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 Format

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

3 3 3

0.667

Hint

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:

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);

Constraints

For $100\%$ of the testdata, $0 \leq M \leq 2147483647$.

Please note that there is no single test point where both $N$ and $K$ reach their maximum values.

Test set index	$N \le$	$K \le$
$1 \sim 3$	$10$	$30$
$4 \sim 6$	$100$	$3$
$7 \sim 9$		$8$
$10$	$50$	$30$

Translated by ChatGPT 5