P3757 [CQOI2017] 老C的键盘 题解

思路

注意到这道题就是AT_dp_t Permutation在树上的版本。

题意就是给你一颗完全二叉树，并给出所有父节点与子节点的大小关系，求当 $n$ 个点的权值是 $n$ 的排列并满足大小关系的排列方案数。

考虑树形dp，设 $dp_{x,i}$ 表示用 $[1,sz_x]$ 的排列填进以 $x$ 为根的子树并且 $x$ 的排名为 $i$ 的方案数。

设当前节点为 $x$，要转移的子节点为 $y$，考虑枚举 $x$ 在合并后的排名 $i$，$y$ 在合并后的排名 $j$，$x$ 在合并前的排名 $k$，$y$ 在合并前的排名 $l$。

当合并后 $i<j$ 时，有：

$$dp_{x,i}\leftarrow dp_{x,k}\times dp_{y,l}\times \binom{i-1}{k-1}\times \binom{j-i-1}{l-1-(i-k)}\times \binom{sz_x+sz_y-j}{sz_y-l}$$

可以看为将排名分为三部分：小于 $i$ 的，在 $i$ 和 $j$ 之间的，和大于 $j$ 的三部分，每部分填数的方案数的乘积。

同理，当 $i>j$ 时，有：

$$dp_{x,i} \leftarrow dp_{x,k}\times dp_{y,l}\times \binom{j-1}{l-1}\times \binom{i-j-1}{k-1-(j-l)}\times \binom{sz_x+sz_y-i}{sz_x-k}$$

最后答案即为 $\sum_{\substack{1 \le i \le n}}dp_{1,i}$。

由于树为完全二叉树，枚举子树时间复杂度为 $O(n \log n)$，总时间复杂度为 $O(n^3 \log^2 n)$。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
bool aaa;
int n;
string s;
ll dp[110][110],g[110],f[110],fv[110];
int sz[110];
bool bbb;
ll qpow(ll a,ll b){
	ll ans=1;
	for(;b;b>>=1,a=a*a%mod)if(b&1)ans=ans*a%mod;
	return ans;
}
ll C(ll n,ll m){
	if(n<m)return 0;
	return f[n]*fv[m]%mod*fv[n-m]%mod;
} 
void dfs(int x){
	sz[x]=1;
	dp[x][1]=1; 
	int y=x*2;
	if(y>n)return ;
	dfs(y);//递归左子节点 
	sz[x]+=sz[y];
	for(int i=1;i<=sz[x];i++){//由于此时x的子树只有一个点，合并比较简单 
		int l=1,r=sz[x];
		if(s[y]=='<')l=i+1;
		else r=i-1;
		for(int j=l;j<=r;j++){
			g[i]=(g[i]+dp[y][j+(i<j?-1:0)])%mod;//g是临时数组 
		}
	}
	memcpy(dp[x],g,sizeof(g));
	memset(g,0,sizeof(g));
	y=x*2+1;
	if(y>n)return ;
	dfs(y);//递归右子节点 
	sz[x]+=sz[y];
	for(int i=1;i<=sz[x];i++){
		if(s[y]=='<'){
			for(int j=i+1;j<=sz[x];j++){
				for(int k=1;k<=min(sz[x]-sz[y],i);k++){
					for(int l=1;l<=min(sz[y],j);l++){
						if(l<1||k<1)continue;
						if(l+k<=j&&l+k+min(sz[x]-sz[y]-1,(j-i-1))>=j){//注意这里的判断条件十分重要！！！ 
							g[i]=(g[i]+dp[x][k]*dp[y][l]%mod*C(i-1,k-1)%mod*C(j-i-1,l-1-(i-k))%mod*C(sz[x]-j,sz[y]-l)%mod)%mod;//转移 
						}
					}
				}
			}
		}
		else{
			for(int j=1;j<i;j++){
				for(int k=1;k<=min(sz[x]-sz[y],i);k++){
					for(int l=1;l<=min(sz[y],j);l++){
						if(l<1||k<1)continue;
						if(l+k<=i&&l+k+min(sz[y]-1,i-j-1)>=i){//注意这里的判断条件十分重要！！！ 
							g[i]=(g[i]+dp[x][k]*dp[y][l]%mod*C(j-1,l-1)%mod*C(i-j-1,k-1-(j-l))%mod*C(sz[x]-i,sz[x]-sz[y]-k)%mod)%mod;
						}
					}
				}
			}
		}
	}
	memcpy(dp[x],g,sizeof(g));
	memset(g,0,sizeof(g));
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	f[0]=fv[0]=1;
	for(int i=1;i<=n;i++){
		f[i]=f[i-1]*i%mod;
		fv[i]=qpow(f[i],mod-2); 
	}
	cin>>s; 
	s="  "+s;
	dfs(1);
	ll ans=0;
	for(int i=1;i<=n;i++){
		ans=(ans+dp[1][i])%mod;//统计答案 
	}
	cout<<ans; 
	return 0;
}

思路

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

第一眼的误区：拓扑排序

首先，题目给出的所有边的关系，构成了一棵完全二叉树。每条边给了我们大于或者小于的关系，所以我们可以把这棵树上每条边看成是一条有向边，那么我们可以对这棵树进行拓扑排序。然后按照拓扑排序的顺序，依次填入 $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$ 小的位置肯定都比 $u$ 小。

代码实现细节

预处理组合数

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

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;
}

AI 使用声明

本文使用 AI 工具检测格式是否符合洛谷题解的要求，并修改不符合要求的部分。