题意

有一个长为\(n(n<=50)\)的整数序列\(A\)，每个数都是随机生成的，并且每个数在\(1-n\)的范围内等概率生成。你的任务是计算有多少长度为\(n\)的排列(值域是\(1-n\))任意位置满足\(p_i<=a_i\)，求期望的排列数量

输出要求

答案至少保留标准答案的前九位

解法1

玩两组数据发现答案是\(\frac{(n!)^2}{n^n}\)，直接算就完了……

解法2

由于本人太蒻了，模拟赛上只想到了\(O(n^5)\)的dp

先进行一步转化，考虑\(1-n\)之间的数在\(A\)中出现的次数，记其为\(b_i\)

显然有\(b_i\)的前缀和要小于等于\(i\)，否则答案为\(0\)

考虑设\(dp_{i,j,k}\)表示\(1~i\)中的数选了\(j\)个，\(1-i\)的排列有\(k\)个不能选的方案数

转移方程为\(dp_{i,j,k}=\sum\limits_{x=1}^j\sum\limits_{y=0}^{x-1}dp_{i-1,j-x,k+y}*A_{k+y+1}^{y+1}*C_j^x;\)

如果\(k>0\)的话还要加上\(dp_{i-1,j,k-1}\)

意思是选x个物品i，\(i\)在排列中覆盖了\(y\)个，后面的两个组合数分别为排列的方案数和把前\(i\)个数在序列\(A\)中放置的方案数，不理解的话可以手玩一下~~（我推了2h）~~

代码

#include<bits/stdc++.h>
using namespace std;
int n;
double dp[61][61][61],C[110][110],a[110];
int main(){
	cin>>n;
	a[0]=1;
	for(int i=1;i<=n;i++) a[i]=a[i-1]*i;
	C[0][0]=1;
	for(int i=1;i<=2*n;i++){
		C[i][0]=1;
		for(int j=1;j<=i;j++) C[i][j]=C[i-1][j-1]+C[i-1][j];
	}
	dp[1][1][0]=1.0/n;
	dp[1][0][1]=1.0/n;
	for(int i=2;i<=n;i++){
		for(int j=0;j<=i;j++){
			for(int k=0;k<=i;k++){
				if(k) dp[i][j][k]=dp[i-1][j][k-1];
				for(int x=1;x<=j;x++){
					for(int y=0;y<x;y++){
						dp[i][j][k]+=dp[i-1][j-x][k+y]*C[k+y+1][y+1]*a[y+1]*C[j][x];
					}
				}
				dp[i][j][k]/=n;
			}
		}
	}
	printf("%.9lf\n",dp[n][n][0]);
	return 0;
}