problem

luogu-P3757

solution

$\text{observation}:$ $h_{i/2}-h_i$ 的大小关系，其实就是个二叉树的大小关系。

这很类似之前的排列 $dp$ ，迁移过来，我们尝试 $f(i,j):i$ 在子树内第 $j$ 小的方案数。

当所有符号都是一个方向的时候，就是 [ZJOI2010]排列计数的题解，所以我们类比这里应该也是有组合数计算转移的。

同样是编号划分离散化的理解。

假设当前点为 $u$，儿子为 $v$，枚举 $u$ 为其所在连通块的第 $i$ 小，$v$ 为其所在联通块的第 $j$ 小：

• $h_u<h_v$。

  考虑合并后，$u$ 可能在新大小为 $si{z}_u+si{z}_v$ 的连通块中的排名。

  这就要看 $v$ 所在联通块前 $j$ 小的数与 $h_u$ 的关系了。

  但一定不会到 $i+j$。

  所以，枚举合并后 $u$ 的排名为 $k$，$i\le k<i+j$。

  $f(u,k)\leftarrow f(u,i)\ast f(v,j)\ast \left(\genfrac{}{}{0ex}{}{k-1}{i-1}\right)\ast \left(\genfrac{}{}{0ex}{}{si{z}_u+si{z}_v-k}{si{z}_u-i}\right)$

• $h_u>h_v$。

  转移方程式和原理同上一种情况，只是 $k$ 的范围有所变化，$i+j\le k\le i+si{z}_v$。

时间复杂度为 $O(n^3)$。

前缀和优化 $O(n^2)$ 可以看[HEOI2013]SAO的题解。

code

#include <bits/stdc++.h> using namespace std; #define int long long #define mod 1000000007 #define maxn 105 char s[maxn]; int n; int c[maxn][maxn], f[maxn][maxn], g[maxn], siz[maxn];void dfs( int u ) {f[u][1] = siz[u] = 1;for( int o = 0;o <= 1;o ++ ) {int v = (u << 1) + o;if( v > n ) break;dfs( v );memcpy( g, f[u], sizeof( f[u] ) );memset( f[u], 0, sizeof( f[u] ) );for( int i = 1;i <= siz[u];i ++ )for( int j = 1;j <= siz[v];j ++ )if( s[v] == '>' ) {for( int k = i + j;k <= i + siz[v];k ++ )(f[u][k] += g[i] * c[k - 1][i - 1] % mod * f[v][j] % mod * c[siz[u] + siz[v] - k][siz[u] - i]) %= mod;}else {for( int k = i;k < i + j;k ++ )(f[u][k] += g[i] * c[k - 1][i - 1] % mod * f[v][j] % mod * c[siz[u] + siz[v] - k][siz[u] - i]) %= mod;}siz[u] += siz[v];} }signed main() {scanf( "%lld %s", &n, s + 2 );for( int i = 0;i <= n;i ++ ) {c[i][0] = c[i][i] = 1;for( int j = 1;j < i;j ++ )c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;}dfs( 1 );int ans = 0;for( int i = 1;i <= n;i ++ ) (ans += f[1][i]) %= mod;printf( "%lld\n", ans );return 0; }

总结

以上是生活随笔为你收集整理的[CQOI2017] 老C的键盘（树形dp + 组合数）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。