算法
(树上问题、组合数学) $O(D)$
$X =$ 左边深度为 $k$ 的顶点数 $\times$ 右边深度为 $D - k$ 的顶点数
$M = \max(k, D - k)$
而高度大于等于 $M$ 的子树有 $2^{N - M} - 1$ 个
对于每个 $k$ 的贡献是 $(2^{N - M} - 1) \times X$
我们枚举 $k=0 \sim D$ 即可
C++ 代码
#include <bits/stdc++.h>
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::max;
using std::vector;
using mint = modint998244353;
int main() {
int n, d;
cin >> n >> d;
vector<mint> two(n + 1);
two[0] = 1;
rep(i, n) two[i + 1] = two[i] * 2;
mint ans;
rep(i, d + 1) {
int j = d - i;
if (i >= n) continue;
if (j >= n) continue;
mint now = two[n - max(i, j)] - 1;
now *= two[max(i - 1, 0)];
now *= two[max(j - 1, 0)];
ans += now;
}
ans *= 2;
cout << ans.val() << '\n';
return 0;
}