显然不能直接考虑图长什么样
考虑如何构造一个图，让一个 $B$ 序列尽可能合法
发现对于一些点，如果能让它们先弱联通，（一个节点指向下一个节点，形成一条链）
那么对于最后一个节点，它想缩几个联通块都行，可以证明，这样可以包括所有其他情况形成的 $B$ 序列
感性理解因为这样可以消耗最少的边来达到我们想要的联通块数，多出来的边就有更多选择，当然也包括连废边（联通块内的点往联通块连）
然后就只要考虑这一种 '链' 的情况就好了
考虑 $dp$ ，设 $F[i][j]$ 表示到第 $i$ 条边（即 $B$ 序列的第 $i$ 个数），当前联通块个数为 $j$ （即 $B$ 序列第 $i$ 个数值为 $j$ ）时的方案数
但是发现这还不够，因为可能在第 $i$ 条边时，不存在联通块个数为 $j$ 的情况
那么就会导致一个合法状态转移到一个废状态，然后再转移给合法状态，导致答案变大
而且又发现对于不同的情况，$i$ 和 $j$ 之间的限制是不一样的
所以考虑多设一维 $k$ 来保证对于一个状态 $i,j$， $k$ 的限制是一样的
设 $F[i][j][k]$ ， $i,j$ 意义同上， $k$ 表示此时有 $k-1$ 条边用于往回连减少联通块数量（$k-1$只是为了保证 $k$ 为正数，比较方便）
那么用来构造 '链' 的边有 $i-(k-1)$ 条，并且为了让这 $n$ 个点变成 $j$ 个联通块，我们要用到链上的 $n-j$ 条边
所以有一个限制： $i-(k-1)>=n-j$
发现对于不同的联通块数量 $j$ ，边数也是有上限的
最多情况就是一个联通块有 $n-j+1$ 个点，剩下 $j-1$ 个联通块只有自己一个点，然后大的联通块每个点都往所有其他点连边，小的联通块就只能它们之间连边
那么最大边数为 $(n-j+1)*(n-1)\ +\ (j-2+j-3+j-4+j-5+...+1)\ =\ (n-j+1)*(n-1)+(j-1)*(j-2)/2$
然后考虑具体转移（以下均为合法状态）
当前边连废边：$F[i][j][k]+=F[i-1][j][k]$
当前边回连用来减少联通块个数： $F[i][j][k]+=\sum_{h=j+1}^{n}F[i-1][h][k-1]$
然后第二个转移显然前缀和优化，再把 $i$ 滚动掉
空间够了，但是时间还是不够，发现这个 $k$ 很麻烦，把之前的式子变一下 $i-(k-1)>=n-j\rightarrow i+1-n+j>=k $
发现当 $i>=2n$ 时，$k$ 总是合法的
所以 $F$ 只要处理到 $2n$ ，然后剩下的部分换一个数组 $G[i][j]$ 来维护，$G[i][j]$ 的意义和一开始设的 $F[i][j]$ 是一样的
然后同样可以前缀和优化
最后复杂度就是 $O(n^3)$
#include#include #include #include #include using namespace std;typedef long long ll;inline int read(){ int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f;}const int N=407,mo=1e9+7;inline int fk(int x) { return x>=mo ? x-mo : x; }int n,lim[N],F[2][N][N],G[N][N];int sumF[2][N][N],sumG[N][N],ans[N*N];int main(){ n=read(); for(int i=1;i<=n;i++) lim[i]=(n-(i-1))*(n-1)+(i-1)*(i-2)/2; F[1][n][1]=ans[1]=1; int Mx=min(n*(n-1),n<<1); for(int i=n;i>=1;i--) sumF[1][i][1]=1; for(int i=2;i<=Mx;i++) { int op=i&1; for(int j=1;j<=n;j++) for(int k=1;k<=n;k++) F[op][j][k]=0; for(int j=1;j<=n;j++) if(i<=lim[j]) for(int k=1;k<=n;k++) if( i-(k-1)>=n-j ) F[op][j][k]=fk(F[op^1][j][k] + sumF[op^1][j+1][k-1]); for(int j=n;j>=1;j--) for(int k=1;k<=n;k++) { sumF[op][j][k]=fk(sumF[op][j+1][k]+F[op][j][k]); ans[i]=fk(ans[i]+F[op][j][k]); } } for(int j=1;j<=n;j++) for(int k=1;k<=n;k++) G[0][j]=fk(G[0][j]+F[0][j][k]); for(int j=n;j>=1;j--) sumG[0][j]=fk(sumG[0][j+1]+G[0][j]); for(int i=Mx+1;i<=n*(n-1);i++) { int op=i&1; for(int j=1;j<=n;j++) G[op][j]=0; for(int j=1;j<=n;j++) if(i<=lim[j]) G[op][j]=fk(G[op^1][j]+sumG[op^1][j+1]); for(int j=n;j>=1;j--) { sumG[op][j]=fk(sumG[op][j+1]+G[op][j]); ans[i]=fk(ans[i]+G[op][j]); } } for(int i=1;i<=n*(n-1);i++) printf("%d ",ans[i]); return 0;}