There exists an obvious solotion with the time complexity of \(O(n^7)\), but it’s not much faster than \(O(n^8)\).

We will definitely use DP to solve this kind of counting problem. We will build the shortest path tree.That is to say, we should divide the nodes into several layers and edges only exist in nodes which are in the same layers or adjecent layers. So the length of the shortest path equals to the depth of the node in the ‘tree’. Here is a figure helping you to understand.

We should ensure that every node has an edge leading to a node in the higher layer.

What kind of information is necessary? We should record the number of the node in the layers with odd depths (\(i\)) and that of the node in the layers with even depths (\(j\)). Which layer we are current in is also important (\(0/1\)). And as we are adding nodes to a deeper layer, we need to know the number of nodes in the deepest layer temporarily \((lst)\). And definitely we should record how many edges we have added \((m)\). So the number of the possible states is already \(O(n^5)\). To achieve an overall time complexity of \(O(n^7)\), we can only traverse \(O(n^2)\) kinds of transfers.

First of all, we add the edges between the current layer.This part is easy because we only need to traverse the number of edges. We can write out the formula

\[ dp_{i,j,0/1,lst,m+t} \leftarrow dp_{i,j,0/1,lst,m+t} + dp_{i,j,0/1,lst,m} \times \binom{\binom{lst}{2}}{t} \]

Next, we add the edges between layers. We should record the number of nodes in the next layers, so we keep \(g_{i,j,0/1,lst,m,new}\). Every time, we make \(new \leftarrow new+1\), and traverse the number of edges we add (apparently it’s between \(1\) and \(lst\)). We can write out the formula:

\[ g_{i,j,0/1,lst,m+e,new+1} \leftarrow g_{i,j,0/1,lst,m+e,new+1} + g_{i,j,0/1,lst,m,new} \times \binom{lst}{e} \]

Initially, \(g_{i,j,0/1,lst,m,0}=dp_{i,j,0/1,lst,m}\).

Finally, we should number the nodes,that is to say (supposing that we will add nodes in \(i\))

\[ dp_{i+new,j,1/0,new,m} \leftarrow dp_{i+new,j,1/0,new,m} + g_{i,j,0/1,m,lst,new} \times \dbinom{n-i-j}{new} \]

The overall time complexity is \(O(n^7)\).

My Code:

#include<bits/stdc++.h>
#define int long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=16,MAXM=500;
int n,t,M,MOD,C[MAXM][MAXM],dp[MAXN][MAXN][MAXM][2][MAXN],g[MAXN][MAXN][MAXM][2][MAXN][MAXN];
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>MOD,M=n*(n-1)/2,t=n/2;
	ffor(i,0,M+10) {C[i][0]=1;ffor(j,1,i) C[i][j]=(C[i-1][j]+C[i-1][j-1])%MOD;}
	dp[1][0][0][0][1]=1;
	ffor(j,1,t) ffor(o,0,t) {
		int d=j+o-1,u=(j+o)*(j+o-1)/2;
		roff(m,u,d) ffor(op,0,1) ffor(lst,0,max(o,j)) if(dp[j][o][m][op][lst]) {
			int al=lst*(lst-1)/2;
			ffor(e,1,al) dp[j][o][m+e][op][lst]=(dp[j][o][m+e][op][lst]+dp[j][o][m][op][lst]*C[al][e])%MOD;
		}
		ffor(lst,1,j) {
			int op=0;
			ffor(m,d,u) g[j][o][m][op][lst][0]=dp[j][o][m][op][lst];
			ffor(m,d,M) ffor(ad,0,t-o-1) if(g[j][o][m][op][lst][ad]) ffor(e,1,lst) g[j][o][m+e][op][lst][ad+1]=(g[j][o][m+e][op][lst][ad+1]+g[j][o][m][op][lst][ad]*C[lst][e])%MOD;
			ffor(ad,1,t-o) ffor(m,d,M) dp[j][o+ad][m][1][ad]=(dp[j][o+ad][m][1][ad]+g[j][o][m][0][lst][ad]*C[n-o-j][ad])%MOD;
		}
		ffor(lst,1,o) {
			int op=1;
			ffor(m,d,u) g[j][o][m][op][lst][0]=dp[j][o][m][op][lst];
			ffor(m,d,M) ffor(ad,0,t-j-1) if(g[j][o][m][op][lst][ad]) ffor(e,1,lst) g[j][o][m+e][op][lst][ad+1]=(g[j][o][m+e][op][lst][ad+1]+g[j][o][m][op][lst][ad]*C[lst][e])%MOD;
			ffor(ad,1,t-j) ffor(m,d,M) dp[j+ad][o][m][0][ad]=(dp[j+ad][o][m][0][ad]+g[j][o][m][1][lst][ad]*C[n-o-j][ad])%MOD;
		}
	}
	ffor(m,n-1,n*(n-1)/2) {
		int ans=0;
		ffor(op,0,1) ffor(lst,0,t) ans+=dp[t][t][m][op][lst];
		cout<<ans%MOD<<' ';
	}
	return 0;
}