分析
题目要求在一共加入若干条边是的不同B序列的个数；方便统计，我们不妨让一个B序列对应一种特定的操作来构造，具体如下
从1开始按从小到大加入点，始终维护一个顺序为加点次序的链；每次加入一条有向边
不会影响SCC个数的
1）连上新点：链末尾与新点连
2）连上废边：加上一条不改变强连通情况的边，不改变链
（两个决策每次必须只选一种，钦定为能加点加点，否则考虑连废边）
会影响的SCC个数
3）把链上与1强连通的部分（钦定为链的前缀）向后扩展若干
应注意到任意时刻SCC的数目为n-(j+1)，n是图的点集大小，j是当前与1强连通的点集大小。
这样的构造与B序列是一一对应的，于是我们可以考虑计数dp，设f[i,j,k]为已经加入了i条边，与1强连通的链前缀长度为j+1，除此之外还有长度k的不同的B序列的个数。
转移和一些约束如下
f[0,0,0]=1
f[i,j,k]->f[i+1,j,k+1] j+1+k<n
f[i,j,k]->f[i+1,j,k] j+1+k==n且j*(j+1)+k(k-1)/2+(j+1)*k>i （注意是有向边哦）
f[i,j,k]->f[i+1,j+t,k-t] 0<t<=k 需要前缀和优化
实现
先留坑好了。 以下是暴力代码（80）
#include <bits/stdc++.h>
using namespace std;
const int mod=1e9+7;inline void add(int&x,int y) {
if((x+=y)>=mod) x-=mod;
}int n,now,nxt=1;
int f[2][401][401],t[401][401];int main() {
scanf("%d",&n);
f[now][0][0]=1;
for(int i=0; i<n*(n-1); ++i,now=nxt,nxt^=1) {
for(int j=0; j<n; ++j) {
for(int k=0; j+k<n; ++k) {
if(!f[now][j][k]) continue;
if(j+1+k<n) add(f[nxt][j][k+1],f[now][j][k]);
else if(j*(j+1)+k*(k-1)/2+(j+1)*k>i) add(f[nxt][j][k],f[now][j][k]);
if(k>0) add(t[j+1][k-1],f[now][j][k]);
f[now][j][k]=0;
}
}
for(int j=0; j<n; ++j) {
for(int k=0; j+k<n; ++k) {
add(f[nxt][j][k],t[j][k]);
if(k>0) add(t[j+1][k-1],t[j][k]);
t[j][k]=0;
}
}
int ans=0;
for(int j=0; j<n; ++j) {
for(int k=0; j+k<n; ++k) {
add(ans,f[nxt][j][k]);
}
}
printf("%d ",ans);
}
return 0;
}
优化状态数目并吸氧的代码
// luogu-judger-enable-o2
#include <bits/stdc++.h>
using namespace std;const int N=400+5;
const int mod=1e9+7;int n;
int now,nxt=1,f[2][N][N],t[N][N];
#define push(c,x,y) sta[c][++top[c]]=make_pair(x,y)
int mx,top[2],tmp[N];
pair<int,int> sta[2][20*N*N];
bool vis[N];inline void add(int&x,int y) {
if((x+=y)>=mod) x-=mod;
}
int main() {
scanf("%d",&n);
f[now][0][0]=1;
push(now,0,0);
for(int i=0; i<n*(n-1); ++i,now=nxt,nxt^=1) {
top[nxt]=0;
for(int p=1; p<=top[now]; ++p) {
int j=sta[now][p].first;
int k=sta[now][p].second;
//printf("|%d,%d>,",j,k);
if(!f[now][j][k]) continue;
if(j+1+k<n) {
add(f[nxt][j][k+1],f[now][j][k]);
push(nxt,j,k+1);
} else if(j*(j+1)+k*(k-1)/2+(j+1)*k>i) {
add(f[nxt][j][k],f[now][j][k]);
push(nxt,j,k);
}
if(k>0) {
add(t[j+1][k-1],f[now][j][k]);
vis[j+k]=true;
}
f[now][j][k]=0;
}
int c=0,pre=top[nxt];
for(int s=0; s<n; ++s) if(vis[s]) {
vis[s]=false; tmp[++c]=s;
}
for(int j=0; j<n; ++j) {
for(int p=c; p; --p) {
int k=tmp[p];
if(k<0) break;
add(f[nxt][j][k],t[j][k]);
if(f[nxt][j][k]) push(nxt,j,k);
if(k>0) add(t[j+1][k-1],t[j][k]);
t[j][k]=0; tmp[p]--;
}
}
merge(sta[nxt]+1,sta[nxt]+pre+1,sta[nxt]+pre+1,sta[nxt]+top[nxt]+1,sta[nxt]+1); //归并
top[nxt]=unique(sta[nxt]+1,sta[nxt]+top[nxt]+1)-sta[nxt]-1;
int ans=0;
for(int p=1; p<=top[nxt]; ++p) {
add(ans,f[nxt][sta[nxt][p].first][sta[nxt][p].second]);
}
printf("%d ",ans);
}
return 0;
}
