[Fortuna OJ]6352 – 给(ca)题解

主要思路

首先,叶子结点为\(k\)时,整个完整的二叉树存在\(2k – 1\)个节点。我们设置一个 DP 来进行计数。

考虑设置状态\(dp[i][j]\)为当前树已有\(i\)个节点,且有当前加入的节点到根的路径有\(j\)单位长度。考虑以下转移:

\[ dp[i + 1][j + 1] += dp[i][j] \\ dp[i + 1][j – 1] += dp[i][j] \]

向新的节点加入统计数据:多了一个叶子结点,要么向左走,加深当前的路径;要么补上最后一个向左走的右节点。

然后就可以写代码了。

代码

// FOJ6353.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 5050, mod = 998244353;

int dp[MAX_N << 1][MAX_N], n, m;

int main()
{
    freopen("ca.in", "r", stdin);
    freopen("ca.out", "w", stdout);
    scanf("%d%d", &m, &n);

    dp[1][0] = 1;

    for (int i = 1; i < (n << 1) - 1; i++)
    {
        for (int j = 0; j < min(m, i); j++)
        {
            dp[i + 1][j - 1] = (1LL * dp[i + 1][j - 1] + dp[i][j]) % mod;
            dp[i + 1][j + 1] = (1LL * dp[i + 1][j + 1] + dp[i][j]) % mod;
        }
    }
    for (int i = 1; i <= n; i++)
        printf("%d\n", dp[(i << 1) - 1][0]);
    return 0;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注