1875F - Jellyfish and EVA - CodeForces Solution

#include<bits/stdc++.h>
#define int long long
#define db long double
using namespace std;
const int N=5077;
vector<int> a[N];
db g[N][N],f[N];
bool cmp(int x,int y){return f[x]>f[y];}
void solve()
{
	int n,m;
	cin>>n>>m;
	for(int i=1; i<=n; i++) for(int j=1; j<=i; j++) g[i][j]=(db)1/i;
	g[1][1]=1.0;
	g[2][1]=0.5,g[2][2]=0.0;
	g[3][1]=g[3][2]=g[3][3]=1.0/3.0;
	for(int i=4; i<=n; i++)
	{
		g[i][1]=g[i][2]=1.0/i;
		for(int j=3; j<i; j++) 
			g[i][j]=g[i-2][j-2]*(j-2)/i+g[i-2][j-1]*(i-j)/i;
		if(i%2==0) g[i][i]=0.0;
		else g[i][i]=(db)1/i;
	}
	for(int i=1; i<=n; i++) a[i].clear();
	for(int i=1; i<=m; i++)
	{
		int x,y;
		cin>>x>>y;
		a[x].push_back(y);
	}
	f[n]=1;
	for(int i=n-1; i>=1; i--)
	{
		f[i]=0;
		sort(a[i].begin(),a[i].end(),cmp);
		for(int j=0; j<a[i].size(); j++)
			f[i]+=f[a[i][j]]*g[a[i].size()][j+1];
	}
	cout<<f[1]<<"\n";
}
signed main()
{
	ios::sync_with_stdio(false); cin.tie(0),cout.tie(0);
	cout<<fixed<<setprecision(10);
	int T=1;
	cin>>T;
	while(T--)
	{
		solve();
	}
}