[洛谷 P4099 HEOI2013] SAO

题目链接

大致题意:

给出一个树形图,求有多少种不同的拓扑序

解题思路:

如果你把这题看成拓扑图，多半你已经凉了……

树形图,那么就和树没有什么区别,我们完全可以把它看作是一棵树,然后考虑方向的限制

通常我们在树上跑$dp$,就是在做树形$dp$,设$f[i]$表示以$i$为根的子树不同的拓扑方案数

然而在转移的过程中可以发现,转移的序列是这样子的:$xxxxxxUxxxxxxVxxxxxx$,也就是说我们无法确定序列到底是什么样的,这时,我们需要在增加一维,帮助我们确定序列,我们加一维$i$在拓扑序列中的排名,这样我们就可以准确得知拓扑序列的样子

最终确定转移方程为:$f[i][j]$表示i在子树$i$中拓扑序排名为$j$的方案数

转移让人头疼啊

$sz[i]$表示$i$子树的节点数

假设现在我们有两个树$u,v,u$是父亲(也就是说$v$其实是$u$的一个子树,只是还没转移) $u$的拓扑序小于$v$的拓扑序(假设条件,即$u<v$),我们讨论从$f[u][p1]$和$f[v][p2]$转移得到新的$f[u][p3]$,转移前,$u$在原序列排名为$p1$, $v$在原序列排名为$p2$,转移后,$u$在新序列排名为$p3$,$v$在新序列排名为$p4$,且$p3<p4$

那么在$u$的子树中,$p1$左边的点一定在$p3$的左边(因为都同$u$比较)

又因为$p3<p4$,那么$v$原序列中$[p2,s{z}_y]$都在$p3$右边,$[1,p2-1]$有一些可以在$p3$左边,有一些可以在$p3$右边

得出$p3$左边序列数的数量限制为:$p1-1<=p3-1<=p1-1+p2-1$,即$p1<=p3<=p1+p2-1$

接下来考虑$p3$左边的情况,左边有$p3-1$个点,一定有$p1-1$个点来自$u$的原序列,所以左边的方案数为$C_{p3-1}^{p1-1}$,右边情况,有$s{z}_u+s{z}_v-p3$个点,一定有$s{z}_u-p1$个点来自$u$的原序列,所以右边的方案数为$C_{s{z}_u+s{z}_v-p3}^{s{z}_u-p1}$

综上，从$f[u][p1]$,$f[v][p2]$转移到新的$f[u][p3]$，而且新序列中$u$在$v$左边，要满足，转移方程$p1<=p3<=p1+p2-1$

转移方程:$f[u][p3]+=f[u][p1]f[v][p2]C_{p3-1}^{p1-1}{C}_{s{z}_u+s{z}_v-p3}^{s{z}_u-p1}$

另一种情况是$v$的拓扑序小于$u$的拓扑序,推导过程同理,$p3$的取值范围发生了变化 $p1+p2<=p3<p1+s{z}_u$

枚举$p1,p2,p3$时间复杂度是$O(n^3)$,考虑优化

for(int p1=1;p1<=sz[u];++p1) for(int p2=1;p2<=sz[v];++p2) for(int p3=p1;p3<=sz[u]+sz[v]-1) 转移方程 

$p2,p3调换顺序$

for(int p1=1;p1<=sz[u];++p1) for(int p3=p1;p3<=p1+sz[v]-1;++p3) for(int p2=p3-p1+1;p3<=sz[v]) 转移方程 

可以把$p2$循环省掉,利用前缀和优化,时间复杂度为$O(n^2)$

头都大了

AC代码:

#include <bits/stdc++.h> #define rep(i, n) for (int i = 1; i <= (n); ++i) using namespace std; typedef pair<int, int> PII; typedef long long ll; const int N = 1010, mod = 1e9 + 7; int n, m; ll f[N][N], dp[N]; //f[i][j]表示i点在i的子树节点中的序列排第j个的方案数 dp[i]表示f[i]的前缀和 int sz[N], c[N][N]; vector<pair<int, int>>e[N]; void dfs(int u, int fa) { 
    //初始化 sz[u] = 1; f[u][1] = 1; for (auto& op : e[u]) { 
    int v = op.first, w = op.second; if (v == fa)continue; dfs(v, u); memcpy(dp, f[u], sizeof dp); memset(f[u], 0, sizeof f[u]); if (w == 1) { 
    for (int p1 = 1; p1 <= sz[u]; ++p1) for (int p3 = p1; p3 < p1 + sz[v]; ++p3) f[u][p3] = (f[u][p3] + 1ll * c[sz[u] + sz[v] - p3][sz[u] - p1] * c[p3 - 1][p1 - 1] % mod * dp[p1] % mod * (f[v][sz[v]] - f[v][p3 - p1] + mod)) % mod; } else { 
    for (int p1 = 1; p1 <= sz[u]; ++p1) for (int p3 = p1 + 1; p3 <= p1 + sz[v]; ++p3) f[u][p3] = (f[u][p3] + 1ll * c[sz[u] + sz[v] - p3][sz[u] - p1] * c[p3 - 1][p1 - 1] % mod * dp[p1] % mod * f[v][p3 - p1]) % mod; } //一定在转移方程的后面 sz[u] += sz[v]; } //前缀和 for (int i = 1; i <= sz[u]; ++i) f[u][i] = (f[u][i] + f[u][i - 1]) % mod; } int main(void) { 
    //预处理组合数 c[0][0] = 1; for (int i = 1; i < N; ++i) { 
    c[i][0] = 1; for (int j = 1; j <= i; ++j) c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod; } int t; cin >> t; while (t--) { 
    int n; cin >> n; //初始化 for (int i = 1; i <= n; ++i)e[i].clear(); memset(sz, 0, sizeof sz); int a, b; char c; for (int i = 1; i < n; ++i) { 
    cin >> a >> c >> b; ++a; ++b; e[a].push_back({ 
    b,c == '<' }); e[b].push_back({ 
    a,c == '>' }); } dfs(1, -1); cout << f[1][n] << endl; } return 0; }