题意：
n个点的“有向”树，求拓扑排序方案数
Welcome to Sword Art Online!!!
一开始想错了...没有考虑一个点的孩子可以排在父亲后...
为了能转移，给状态加一维，\(f[i][j]\)表示子树i，i排在第j位的方案数
然后，很像树形背包啊，转移枚举孩子子树中k个点在i之前，更新\(f[i][j+k]\)
严格做到每次合并复杂度为 **“已经合并大小*正要合并进去的大小”，那么这个复杂度就是\(O(n^2)\)的，因为一个点对只贡献一次**
真不敢相信我以前的树形背包都写的是\(O(n^3)\)
注意需要用一个新数组保存当前更新得到的值
#include#include #include #include #include using namespace std;typedef long long ll;const int N = 1005, P = 1e9+7;inline int read() { char c=getchar(); int x=0,f=1; while(c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();} return x*f;}int n, u, v, c[N][N];char s[5];struct edge{int v, ne, p;} e[N<<1];int cnt, h[N];inline void ins(int u, int v) { //printf("ins %d %d\n", u, v); e[++cnt] = (edge){v, h[u], 1}; h[u] = cnt; e[++cnt] = (edge){u, h[v], 0}; h[v] = cnt;}int f[N][N], size[N], f_pre[N][N], f_suf[N][N], g[N];void dp(int u, int fa) { size[u] = 1; f[u][1] = 1; for(int i=h[u]; i; i=e[i].ne) { int v = e[i].v, p = e[i].p; if(v == fa) continue; dp(v, u); for(int j = 0; j <= size[u] + size[v]; j++) g[j] = 0; for(int j = 1; j <= size[u]; j++) for(int k = 0; k <= size[v]; k++) { ll t = p ? f_suf[v][k+1] : f_pre[v][k]; g[j+k] = (g[j+k] + (ll) c[j-1+k][k] * c[size[u]-j+size[v]-k][size[v]-k] %P * f[u][j] %P * t) %P; } for(int j = 0; j <= size[u] + size[v]; j++) f[u][j] = g[j]; size[u] += size[v]; } for(int i = 1; i <= size[u]; i++) f_pre[u][i] = (f_pre[u][i-1] + f[u][i]) %P; for(int i = size[u]; i >= 1; i--) f_suf[u][i] = (f_suf[u][i+1] + f[u][i]) %P;}int main() { freopen("in", "r", stdin); int T = read(); c[0][0] = 1; for(int i=1; i