专栏文章

P12415 题解

zztd___
P12415题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipexfvb
此快照首次捕获于
2025/12/03 10:53
3 个月前
此快照最后确认于
2025/12/03 10:53
3 个月前
查看原文
注意：本文的“方案数”一词指代的不是同一个东西的方案数，请谨慎辨别。
首先可以发现：我们没必要考虑每一行的结点如何排列，只需要知道每行的结点个数即可。
证明：
只要某一行上的结点数量确定（假设等于 xx），那么，通过排列这一行所产生的方案数是固定的，即 CmxC^x_m（从 mm 个空位中选择 xx 个，让它们变成树的结点）。
然后，每一行的结点的排列方式对于后面和前面的点也是没有影响的。
对于下面的点：我们计算方案时，只关心下面的点能接在多少个点的后面（即能成为多少个点的儿子），而父节点具体的位置不会对方案数产生影响。
对于上面的点：感性理解一下。假设上面的点位置已经固定，我们从下面的点开始构树时，只需要考虑下面的点能成为多少个点的儿子，而在哪一个位置成为儿子节点对总方案数是不会有影响的。
于是可以考虑搜索。由于根很特殊，所以我们把根单独算。枚举根下面的每一行放多少个点，然后分开计算答案。
然后，对于其中的某一层，我们设上面总共有 ss 个点（这意味着这一层的点可以成为多少个点的儿子结点），然后上面那些点构造出来的树总共有 ww 种形态，且我们打算在这一行上面放 ii 个点。
显然，到下一行的时候 ss 会加上 ii，我们考虑 ww 如何变化。
我们发现下一行的 ww （即从第一行到这一行这一棵“部分树”的形态数量）被 33 个因素影响着：
  1. 上面所有点的排列方案数（即这一行的 ww）。
  2. 这一行所有点的排列方案数（即 CmiC^i_m，一开始解释过）。
  3. 这一行的每个点分别接到哪一个点下面。
因为上面总共有 ss 个点，所以这一行的每一个点有 ss 个选择。根据乘法原理，总方案数就是 ii 个 ss 相乘，即 sis^i。
所以下一行的 ww 就是这一行的 ww 乘上 CmiC^i_m 再乘上 sis^i。
那么，我们的爆搜就可以搜下去了。我们考虑怎么统计整个问题的答案。
显然，我们最终的树形态数，就是搜完以后的 ww。但是不要把根给忘掉了。我们的根可以随便放，可以放在任意一行、任意一列。
所以，枚举根放在哪一行，然后把 ww 的初始值设为 mm 即可。
这样我们需要组合数和快速幂。因为 nn 和 mm 都没那么大，所以组合数可以直接用杨辉三角递推。参见 P5732 & P1226。
看一下爆搜代码。文中的 ss 实际上是 sumsum，ww 实际上是 wayway。
CPP
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = 1e9 + 7;
const int N = 7000;
int C[N][N];
int cal(int n, int m) {
    if (C[n][m]) return C[n][m];
    if (m == 1) return C[n][m] = n;
    if (n == m || m == 0) return C[n][m] = 1;
    if (m > n) return 0;
    return C[n][m] = (cal(n - 1, m) + cal(n - 1, m - 1)) % MOD;
}
int Pow(int a, int b) {
    int r = 1, x = a, p = b;
    while (p) {
        if (p & 1) r = r * x % MOD;
        x = x * x % MOD, p >>= 1;
    }
    return r;
}
int n, m, ans;
void dfs(int step, int sum, int way) {
    if (step == n + 1) {
        ans = (ans + way) % MOD;
    } else {
        for (int i = 0;i <= m;i++) {
            dfs(step + 1, sum + i, cal(m, i) * Pow(sum, i) % MOD * way % MOD);
        }
    }
}
signed main() {
    cin >> n >> m;
    for (int i = 1;i <= n;i++) {
        dfs(i + 1, 1, m);
    }
    cout << ans;
    return 0;
}
通过文章开篇的证明，不难看出，我们的搜索是无后效性的，即不会互相影响。那么我们只要将 ww 作为函数的返回值，然后记忆化一下即可。
CPP
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = 1e9 + 7;
const int N = 7000;
int C[N][N];
int cal(int n, int m) {
    if (C[n][m]) return C[n][m];
    if (m == 1) return C[n][m] = n;
    if (n == m || m == 0) return C[n][m] = 1;
    if (m > n) return 0;
    return C[n][m] = (cal(n - 1, m) + cal(n - 1, m - 1)) % MOD;
}
int Pow(int a, int b) {
    int r = 1, x = a, p = b;
    while (p) {
        if (p & 1) r = r * x % MOD;
        x = x * x % MOD, p >>= 1;
    }
    return r;
}
int dp[85][6500], n, m, ans;
int dfs(int step, int sum) {
    if (dp[step][sum]) return dp[step][sum];
    if (step == n + 1) return dp[step][sum] = 1;
    int all = 0;
    for (int i = 0;i <= m;i++) {
        all = (all + cal(m, i) * Pow(sum, i) % MOD * dfs(step + 1, sum + i)) % MOD;
    }
    return dp[step][sum] = all;
}
signed main() {
    cin >> n >> m;
    for (int i = 1;i <= n;i++)
        ans = (ans + m * dfs(i + 1, 1) % MOD) % MOD;
    cout << ans;
    return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...