固定一种构造方法，使它能够构造出所有可能的序列。
对于一个要构造的序列，把所有点排成一串，若a[i]=a[i-1]，那么从1所在弱连通块往连通块后一个点连，若所有点都在一个连通块里了，就在1所在强连通块中随便连。若a[i]<a[i-1]，那么连一条从后往前的边让若干点与1所在强连通快合并。显然这样可以得到所有可能的序列。
于是前一部分“连弱连通块”用f[i][k][x]表示前i个点在一个弱连通块中，到目前为止序列共减小了k次，1所在连通块大小为x，的方案数（此时边数为i-1+k）。
后一部分用g[i][x]表示图*i条边，1所在连通块大小为x的方案数。
两个状态数都是$O(n^3)$的且可以用前缀和$O(1)$转移，g[][]的初值由f[][][]得到。
#include<cstdio>
#include<algorithm>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
using namespace std; const int N=,mod=1e9+;
int n,f[N][N][N],g[N*N][N],smf[N][N][N],smg[N*N][N],res[N*N]; int inc(int x,int y){ x+=y; return x>=mod ? x-mod : x; } int main(){
freopen("c.in","r",stdin);
freopen("c.out","w",stdout);
scanf("%d",&n); f[][][]=smf[][][]=;
rep(i,,n) rep(k,,i-) rep(x,,i){
f[i][k][x]=f[i-][k][x];
if (k && i<n) f[i][k][x]=inc(f[i-][k][x],smf[i][k-][x-]);
smf[i][k][x]=inc(smf[i][k][x-],f[i][k][x]);
if (i<n) res[i-+k]=inc(res[i-+k],f[i][k][x]);
if (i==n) g[i-+k][x]=inc(g[i-+k][x],f[i][k][x]);
}
rep(i,,n*(n-)) rep(x,,n) if (i<=n*(n-)/+x*(x-)/){
g[i][x]=inc(inc(g[i][x],g[i-][x]),smg[i-][x-]);
smg[i][x]=inc(smg[i][x-],g[i][x]);
}
rep(i,,n*(n-)){
int ans=;
rep(x,,n) ans=inc(ans,g[i][x]);
printf("%d ",inc(ans,res[i]));
}
return ;
}