20 years ICPC Macau station L - random permutation

An integer sequence with length nn, denoted by a_1,a_2,\cdots,a_na1​,a2​,⋯,an​, is generated randomly, and the probability of being 1,2,\cdots,n1,2,⋯,n are all \frac{1}{n}n1​ for each a_iai​ (i=1,2,\cdots,n)(i=1,2,⋯,n).

Your task is to calculate the expected number of permutations p_1,p_2,\cdots,p_np1​,p2​,⋯,pn​ from 11 to nn such that p_i \le a_ipi​≤ai​ holds for each i=1,2,\cdots,ni=1,2,⋯,n.

Input

The only line contains an integer nn (1 \leq n \leq 50)(1≤n≤50).

Output

Output the expected number of permutations satisfying the condition. Your answer is acceptable if its absolute or relative error does not exceed 10^{-9}10−9.

Formally speaking, suppose that your output is xx and the jury's answer is yy. Your output is accepted if and only if \frac{|x - y|}{\max(1, |y|)} \leq 10^{-9}max(1,∣y∣)∣x−y∣​≤10−9.

Inputcopy	Outputcopy
2	1.000000000000

Sample 2

Inputcopy	Outputcopy
3	1.333333333333

Sample 3

Inputcopy	Outputcopy
50	104147662762941310907813025277584020848013430.758061352192

The question ： The length is n Of a Array , Each number is 1,2,3,4..n The odds are 1/n, For all permutations p Array （ Such as 1,2,3.1,3,2.2,1,3.2,3,1.3,1,2.3,2,1）, All subscripts i It's all established pi<ai What are your mathematical expectations .

The meaning of the question is difficult to understand , It's all permutations p Array answers + get up ,p The array is 1,2 answer 2/4, because a Array has 1,2.2,2 Sure , The probability of two is 2/2*2=0.5,p The array is 2,1 The answer is 0.5, The last is 1.000000.

Ideas ： The answer is simple calculation ：(n!*n!)/n^n. There is no formula to calculate directly .

, He should mean before 10 Position right ok, therefore c++ Of long double and py Direct decimal calculation can

  Code ：

#include<bits/stdc++.h>
using namespace std;
#define fo(a,b) for(int i=a;i<=b;i++)
#define inf 0x3f3f3f3f
#define dou long double
#define M 100005
dou res=1,n;
int main(){
    cin>>n;
    for(dou i=0;i<n;i++){
        res*=(n-2*i+i*i/n);
    }
    printf("%.15Lf\n",res);
    return 0;
}

py Code ：

n=(int)(input())
res=1
for i in range(1,n+1):
    res*=1.0/n*i*i
print(res)