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

· · 题解

考察：树形 DP、组合数学。

设 f_{u,k} 表示在以 u 为根的子树中，u 点权值的排名为 k 的方案数。

对于 u,v，若 p_v = u，且要求 a_u < a_v。转移时，枚举有以 v 为根的子树中有多少个点权值小于 a_u。有：

\begin{aligned} f_{u,k} &= \displaystyle\sum_{i = 1}^{\text{siz}_v}\sum_{j = 0}^{i - 1}\binom{k - 1}{j}\binom{\text{siz}_u+\text{siz}_v-k}{\text{siz}_v-j}f_{v,i} f_{u,k - j}\\ &= \sum_{j = 0}^{\text{siz}_v-1}\binom{k-1}{j}\binom{\text{siz}_u+\text{siz}_v-k}{\text{siz}_v-j}f_{u,k-j}\sum_{i=j+1}^{\text{siz}_v}f_{v,i} \end{aligned}

若要求 a_u > a_v，枚举以 v 为根的子树中有多少个点权值大于 a_u。有：

\begin{aligned} f_{u,k}&=\sum_{i=1}^{\text{siz}_v}\sum_{j=0}^{\text{siz}_v-i}\binom{k - 1}{\text{siz}_v-j}\binom{\text{siz}_u+\text{siz}_v-k}{j}f_{v,i}f_{u,k+j-\text{siz}_v}\\ &= \sum_{j = 0}^{\text{siz}_v-1}\binom{k - 1}{\text{siz}_v-j}\binom{\text{siz}_u+\text{siz}_v-k}{j}f_{u,k+j-\text{siz}_v}\sum_{i=1}^{\text{siz}_v-j}f_{v,i} \end{aligned}

前后缀优化后可以做到 O(n^2)。关于树上背包的时间复杂度证明如下：

::::success[证明]

定义 siz \le k 的子树为小子树，其余的为大子树。极大的小子树为，大到不能在与其他任意一棵子树合并的小子树，极小的大子树为，不断合并的过程中，大到恰好满足大子树条件的大子树。

对于极大的小子树内部的合并，显然其内部的每个点对都会在其 LCA 处合并一次，故对于一棵小子树，合并时间复杂度 \mathcal{O}\left(k^2\right)。根据定义，极大的小子树不会互相包含，故总共有 \frac{n}{k} 个极大的小子树，总时间复杂度为 \mathcal{O}\left(nk\right)。

对于极大的小子树，到极小的大子树之间的合并，因为极大的小子树的大小不超过 k，且总和不超过 n，故时间复杂度为 \mathcal{O}\left(nk\right)。

对于极小的大子树，显然其棵数小于 \frac{n}{k}，而且没合并一次，少一棵树。因为单次合并复杂复为 \mathcal{O}\left(k^2\right)，故时间复杂度为 \mathcal{O}\left(nk\right)。

综上，总时间复杂度仍为 \mathcal{O}\left(nk\right) ::::

::::success[代码]

#include<bits/stdc++.h>
#define endl '\n'
//#define MSOD

using namespace std;
using ll = long long;

const int N = 1e2 + 5;
const ll M = 1e9 + 7;

int n;
string s;
vector<pair<int, char>> T[N];
ll bin[N][N];
int siz[N];
ll f[N][N], g[N], pre[N][N], suf[N][N];
void dfs(int u) {
    f[u][1] = 1, siz[u] = 1;
    for(auto [v, w] : T[u]) {
        dfs(v);
        for(int i = 1 ; i <= siz[u] ; i ++) g[i] = f[u][i], f[u][i] = 0;
        fill(f[u] + siz[u] + 1, f[u] + siz[u] + siz[v] + 1, 0);
        if(w == '<') {
            for(int k = 1 ; k <= siz[u] + siz[v] ; k ++) {
                for(int j = max(0, k - siz[u]) ; j < min(k, siz[v]) ; j ++) {
                    f[u][k] += bin[k - 1][j] * bin[siz[u] + siz[v] - k][siz[v] - j] % M * g[k - j] % M * suf[v][j + 1] % M;
                    f[u][k] %= M;
                }
            }
        } else {
            for(int k = 1 ; k <= siz[u] + siz[v] ; k ++) {
                for(int j = max(0, siz[v] - k) ; j < siz[v] + min(0, siz[u] - k) + 1 ; j ++) {
                    f[u][k] += bin[k - 1][siz[v] - j] * bin[siz[u] + siz[v] - k][j] % M * g[j + k - siz[v]] % M * pre[v][siz[v] - j] % M;
                    f[u][k] %= M;
                }
            }
        }
        siz[u] += siz[v];
    }
    for(int i = 1 ; i <= siz[u] ; i ++) pre[u][i] = pre[u][i - 1] + f[u][i], pre[u][i] %= M;
    for(int i = siz[u] ; i >= 1 ; i --) suf[u][i] = suf[u][i + 1] + f[u][i], suf[u][i] %= M;
    return;
}
void TEST() {
    cin>>n>>s;
    s = " " + s;
    for(int i = 1 ; i < n ; i ++) T[(i + 1) / 2].emplace_back(i + 1, s[i]);
    for(int i = 0 ; i <= n ; i ++) {
        bin[i][0] = 1;
        for(int j = 1 ; j <= i ; j ++) bin[i][j] = (bin[i - 1][j - 1] + bin[i - 1][j]) % M;
    }
    dfs(1);
    ll ans = 0;
    for(int i = 1 ; i <= n ; i ++) ans += f[1][i], ans %= M;
    cout<<ans;
    return;
}

signed main() {
    ios::sync_with_stdio(false), cout.tie(0), cin.tie(0);
    int TC = 1;
#ifdef MSOD
    cin>>TC;
#endif
    while(TC --) TEST();
    return 0;
}

::::