题解：P3757 [CQOI2017] 老C的键盘

· · 题解

思路

一篇好的题解，不只是讲这道题怎么做，更应该讲清楚这道题怎么想到这么做。

第一眼的误区：拓扑排序

首先，题目给出的所有边的关系，构成了一棵完全二叉树。每条边给了我们大于或者小于的关系，所以我们可以把这棵树上每条边看成是一条有向边，那么我们可以对这棵树进行拓扑排序。然后按照拓扑排序的顺序，依次填入 1 到 n 的每个点，即可得到一个合法的结果。所以这道题本质上在求拓扑排序的方案数。

我相信很多同学，包括我，看到这道题以后，第一思路都是这样的。因此，开始考虑怎么求拓扑排序方案数，即把这个问题完全看成是一个图论问题了。思考半天以后发现没有特别好的方法可以解决。因此需要换一个思路来考虑。

充分利用信息：树上 DP

考虑到题目给我们的是树，树其实是比一张普通的图有更多性质的，如果我们放弃了树的性质，用图来做题，其实就是浪费了题目中的关键信息。因为题目中要求方案数，因此是树上计数类 DP 问题，状态定义套路一般是“以树上某个点为根的子树，合法的方案数有多少”，然后进行转移。

状态的设计

前面提到的状态，只有一维，显然是不够的。我们要考虑状态的第二个维度是什么。注意本题解是按照思考的思路进行展开，所以先不直接跳转到正确答案，而是先讲述一下同学们可能的第一想法。

按照一般情况下做树上 DP 的经验，我们容易想到这样的状态设计：

用一个二维的状态 dp_{u,i} 表示以 u 为根的子树，当树根位置填 i 这个数字的时候，方案数有多少。

然后我们考虑状态转移，还是按照经验，一般的树上 DP，都是先初始化子树的树根的状态，然后把孩子的状态求好，在把孩子一个一个加进来，和之前的已经加进来的树根和子树进行转移。如果你对这个套路不熟悉，可以先做 P1272 重建道路。如下图所示：

以 u 为根的子树，已经有 4 个点。现在要把 u 的一个孩子 v 加进来，看看加入以后，新的以 u 为根的子树的方案数是多少。图中点里面标的数字是实际上要填写的数，这里只表示一个方案，不是全部的方案数。

仔细思考一下发现上述状态定义并不好转移，因为原来的状态里面，比如 1 这个点已经放进去了。现在以 v 为根的子树里面，还有 1 这个点。一个数字不能用两次，这两种状态是合并不了的。所以我们之前记录的状态有些能合并，有些合并不了，这个转移就做不到了。

关键的思考：相对排名

关键点在于，我们不应该在状态里面指定树根上的点放哪个具体数字，而是应该去指定树根上的点，上面放的数字在整棵树里面的排名是多少。

比如说上图当中，左边的那棵树里面，树根上面放的数字 4，本来的定义是要把数字 4 放在这个点上。但是实际上我们应该把它定义为，把整棵树里面排名第四的数字放在这个点上。图上的数字指的是排名，而不是具体的数字是谁。同样道理，在右边即将加进来的子树当中，我们的树根上的 2 也表示，这个数是在这三个点中排第二的。 这样当两棵树合并的时候，对于原来两棵树各自有一个排名的方案，这个方案在新的答案里面，只要保持每一棵树里面原来的相对排名保持不变，新的数字就可以随便的插入进来，得到一个新的方案。

因此，我们修改一下状态的定义，新的定义为：

用一个二维的状态 dp_{u,i} 表示以 u 为根的子树，当树根位置上填的数字在整棵树中排名第 i 的时候，方案数有多少。

状态转移

还是以这张图为例：

首先我们定义一个数组 sz， 用数组的 sz_v 来表示，以 v 这个点为根的子树当中，总共有多少个点。

然后我们考虑把 u 为根的子树里面，加入以 v 为根的子树里面的所有点。那么首先我们需要先去枚举一个变量 i， 用来表示 u 这个点在原来的树当中的排名。同样我们还需要枚举一个变量 j， 表示 v 为根的子树当中，树根排名是第几。我们发现还需要去知道子树当中有多少个点是比树根 u 要小的，我们不妨定义为 k。

边是大于号的情况

在这里我们首先讨论 v 上面的数字比 u 上面的数字大的情况。这个时候我们发现 k 的范围应该是从 0 到 j-1，因为所有比 v 小的数字，在新的树当中都有可能比 u 要小。当然也有可能所有的数字都比 u 要大，因为我们这里面填写的是相对排名。如果有 k 个点比 u 小的话，那么转移到的新状态就会到 i+k 这个位置上。

那么，我们可以简单地得到一个状态转移方程吗？类似：

dp_{u,i+k} = \sum_{i=1}^{s_u} \sum_{j=1}^{s_v} \sum_{k=0}^{j-1} dp_{u,i} \times dp_{v,j}

不止如此，我们还忽略了一个细节。在原来的树当中，我们有 i-1 个点是比树根小的，新合并进来的子树当中，有 k 个点是比树根小的。这些点在原来各自的树当中的排名是确定的，但是把它们合并到一起之后，它们的排名情况就会变多了。比如子树中排名第一的点，和原来的树当中排名第一的点，谁大呢？

合并以后，比树根小的，总共是 i - 1 + k 个点，在这些点当中，其实我们可以选择 k 个点放在子树里，剩下的点放在原来的树里。这个时候子树和原来树各自排名确定，所以方案数就确定了。这样就是一个组合数问题，我们需要乘一个组合数 \binom{i+k-1}{k}。同理，对于比树根要大的点，我们也需要在父节点和子节点之间进行重新的分配。因此，正确的状态转移方程是：

dp_{u,i+k} = \sum_{i=1}^{s_u} \sum_{j=1}^{s_v} \sum_{k=0}^{j-1} dp_{u,i} \times dp_{v,j} \times \binom{i+k-1}{k} \binom{s_u-i+s_v-k}{s_v-k}

边是小于号的情况

同理，当子树上的点比父亲小的时候，我们发现状态转移规则是不变的，只不过 k 的取值范围，至少要等于 sz_j，因为 v 上的数字都比 u 上的数字小，那么 v 的子树里面 j 个比 v 小的位置肯定都比 $u4 小。

代码实现细节

预处理组合数

因为在状态转移的过程中使用了组合数，所以不如预处理一个杨辉三角，把组合数都算出来。

for (ll i = 0; i <= n; ++i) {
        c[i][0] = c[i][i] = 1;
        for (ll j = 1; j < i; ++j) {
            c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % MOD;
        }
    }

因为每次转移都是在父子之间进行，所以我写了一个函数它的两个参数分别是 u 和 v， 表示现在的父节点是 u， 孩子是 v， 要把孩子里面的所有节点加入到 u 这棵子树的里面。实际上还有一个细节就是，我们首先需要把 dp 数组提前保存出来，并且清零。因为这里还隐藏了一个维度 j。 剩下的转移过程就如代码以及代码里的注释所示。

完整的代码如下。时间复杂度 O(n^3)，足以通过本题。

#include <iostream>

using namespace std;
typedef long long ll;
const ll MAXN = 105;
const ll MOD = 1e9 + 7;

//dp[i][j]表示以i点为树根的子树中，i这个点上填写的数字在子树中排名第j大，方案数
ll n, dp[MAXN][MAXN], sz[MAXN], f[MAXN];
ll c[MAXN][MAXN];
char s[MAXN];

void cal(ll u, ll v) {
    // 父结点是u，孩子是v
    if (v > n) {
        return;
    }
    for (ll i = 1; i <= sz[u]; ++i) {
        f[i] = dp[u][i];
        dp[u][i] = 0;
    }
    for (ll i = 1; i <= sz[u]; ++i) {
        // 之前的所有孩子里面，u排名第i，v排名第j
        for (ll j = 1; j <= sz[v]; ++j) {
            // 再枚举一个k表示v所在的子树里面有多少个点排在u前面
            if (s[v] == '>') {
                // v上的数字大于u，则k最大只能取j-1
                for (ll k = 0; k < j; ++k) {
                    ll t = f[i] * dp[v][j] % MOD;
                    // 总共有i+k-1个点排在u前面，取k个放在子树里面
                    t = t * c[i + k - 1][k] % MOD;
                    // 总共有 sz[u]+sz[v]-i-k个点排在u后面，取sz[v]-k个放在子树里面
                    t = t * c[sz[u] + sz[v] - i - k][sz[v] - k] % MOD;
                    dp[u][i + k] = (dp[u][i + k] + t) % MOD;
                }
            } else {
                // v上的数字小于u，则k从j开始
                for (ll k = j; k <= sz[v]; ++k) {
                    ll t = f[i] * dp[v][j] % MOD;
                    // 总共有i+k-1个点排在u前面，取k个放在子树里面
                    t = t * c[i + k - 1][k] % MOD;
                    // 总共有 sz[u]+sz[v]-i-k个点排在u后面，取sz[v]-k个放在子树里面
                    t = t * c[sz[u] + sz[v] - i - k][sz[v] - k] % MOD;
                    dp[u][i + k] = (dp[u][i + k] + t) % MOD;
                }
            }
        }
    }
    sz[u] += sz[v];
}

int main() {
    cin >> n;
    cin >> (s + 2);
    // 预处理杨辉三角数组
    for (ll i = 0; i <= n; ++i) {
        c[i][0] = c[i][i] = 1;
        for (ll j = 1; j < i; ++j) {
            c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % MOD;
        }
    }
    // 是完全二叉树，可以倒着依次处理每个点
    for (ll u = n; u >= 1; --u) {
        // 首先不考虑孩子，自己一个点排名第一，方案有一种
        dp[u][1] = 1;
        sz[u] = 1;
        cal(u, u * 2);
        cal(u, u * 2 + 1);
    }
    ll ans = 0;
    for (int i = 1; i <= n; ++i) {
        ans = (ans + dp[1][i]) % MOD;
    }
    cout << ans << endl;
    return 0;
}