挺神仙的一题
看看除了dp好像没什么其他办法了
想着怎么构个具体的图出来，然鹅不太现实。
于是我们想办法用几个参数来表示dp数组
加了几条边肯定要的吧，于是加个参数$i$表示已加了$i$条边
这显然是不够的。于是我们又想：强连通分量.....连通块.......
于是加个$j$表示还有$j$个强连通分量
于是dp数组为$f[i][j]$
这是我们发现一个问题，状态$f[i][j]$不一定是合法的。
那dp不就GG了吗
再次撕烤，我们发现每次加上的边无非就3种情况：
1.把2个强连通分量（或链）连成一条链
2.在某个强连通分量中瞎连（没啥用）
3.在1条链上的某点向回连，形成一个环，缩成一个新强连通分量（可以减少任意个强连通分量）
我们设$k-1$条边（dp数组下标$k$为正数较好处理）投入到第3种情况
要生成剩下$j$个强连通的情况，我们最少投入$n-j$条边用于第1种情况
所以$n-j+(k-1)<=i$
我们又发现，要生成剩下$j$个强连通的情况，我们最多共投入的边数$i$是有限制的
最多情况就是1个块有$n-j+1$个点，剩下$j-1$个块只有1个点，蓝后大块每个点连$n-1$条边，小块互相之间弱连通
那么最大边数为$(n-j+1)*(n-1)+(j-2+j-3+j-4+...+1)=(n-j+1)*(n-1)+(j-1)*(j-2)/2$
所以$i<=(n-j+1)*(n-1)+(j-1)*(j-2)/2$
总结一下，即设$f[i][j][k]$表示到第$i$条边，有$j$个强连通分量，$k-1$条边向回连的方案数
限制条件：
$n-j+(k-1)<=i$
$i<=(n-j+1)*(n-1)+(j-1)*(j-2)/2$
转移：
$f[i][j][k]+=f[i-1][j][k]$（第2种情况）
$f[i][j][k]+=\sum_{h=j+1}^{n}f[i-1][h][k-1]$
显然是可以滚动数组+前缀和优化的辣
然鹅复杂度还是太高，主要因为k很麻烦
仔细观察k，发现
$n-j+(k-1)<=i$
$k<=i+j-n+1$
发现$i>=2n$时k总是合法的
于是我们就可以愉快地缩成2维辣
#include<iostream>
#include<cstdio>
#include<cstring>
#define rint register int
using namespace std;
inline int Min(int a,int b){return a<b?a:b;}
const int mod=1e9+;
inline int Md(int x){return x<mod?x:x-mod;}
#define N 405
int n,f[][N][N],sf[][N][N],g[][N],sg[N][N],lim[N],ans[N*N];
int main(){
scanf("%d",&n); int tn=Min(n*(n-),n<<),w=;
for(rint j=;j<=n;++j) lim[j]=(n-j+)*(n-)+(j-)*(j-)/;
f[][n][]=ans[]=;
for(rint j=;j<=n;++j) sf[][n][]=;
for(rint i=;i<=tn;++i,w^=){
for(rint j=;j<=n;++j)
for(rint k=;k<=n;++k)
f[w][j][k]=;
for(rint j=;j<=n;++j) if(lim[j]>=i)
for(rint k=;k<=n;++k) if(i-(k-)>=n-j)
f[w][j][k]=Md(f[w^][j][k]+sf[w^][j+][k-]);
for(rint j=n;j;--j)
for(rint k=;k<=n;++k){
sf[w][j][k]=Md(sf[w][j+][k]+f[w][j][k]);
ans[i]=Md(ans[i]+f[w][j][k]);
}
}w=;
for(rint j=;j<=n;++j)
for(rint k=;k<=n;++k)
g[][j]=Md(g[][j]+f[][j][k]);
for(rint j=n;j;--j) sg[][j]=Md(sg[][j+]+g[][j]);//降维
for(rint i=tn+;i<=n*(n-);++i,w^=){
for(rint j=;j<=n;++j) g[w][j]=;
for(rint j=;j<=n;++j) if(lim[j]>=i)
g[w][j]=Md(g[w^][j]+sg[w^][j+]);
for(rint j=n;j;--j){
sg[w][j]=Md(sg[w][j+]+g[w][j]);
ans[i]=Md(ans[i]+g[w][j]);
}
}
for(rint i=;i<=n*(n-);++i) printf("%d ",ans[i]);
return ;
}