2 条题解
-
0
递推写法
#include <bits/stdc++.h> #define int long long using namespace std; const int MAXN = 2000; const int MOD = 1'000'000'000 + 7; // 求 n 个点，m 层的 AVL 树有多少种 // 实际上 m 是 log n 的级别 int f[MAXN + 5][MAXN + 5]; // 求 n 个点的 AVL 树有多少种 int book[MAXN + 5]; signed main() { ios::sync_with_stdio(false); cin.tie(0); f[0][0] = 1; // 节点个数 for (int n = 1; n <= 2000; n++) { // 层数，某个层树可行但多一层不可行时就不用算了。 for (int m = 1; m <= 2000; m++) { // 左子树节点个数 for (int i = 0; i <= n - 1; i++) { int j = (n - 1) - i; f[n][m] += f[i][m - 1] * f[j][m - 1] % MOD; if (m >= 2) { f[n][m] += f[i][m - 1] * f[j][m - 2] % MOD; f[n][m] += f[i][m - 2] * f[j][m - 1] % MOD; } f[n][m] %= MOD; } if (f[n][m - 1] && !f[n][m]) break; book[n] += f[n][m]; book[n] %= MOD; } } int n; while (cin >> n) cout << book[n] << "\n"; return 0; } -
0
33DAI LV 9 (1/1) @ 2025-4-6 10:40:31
记忆化写法
#include <bits/stdc++.h> #define int long long using namespace std; const int MAXN = 2000; const int MOD = 1'000'000'000 + 7; // 求 n 个点，m 层的 AVL 树有多少种 // 实际上 m 是 log n 的级别 int f[MAXN + 5][MAXN + 5]; // 懒得初始化 f 了，单独开一个判断有没有记忆过 bool vis[MAXN + 5][MAXN + 5]; int cal(int n, int m) { if (vis[n][m]) return f[n][m]; vis[n][m] = true; if (m == 0) return f[n][m] = (n == 0); // 左边节点数量 int res = 0; for (int i = 0; i <= n - 1; i++) { int j = (n - 1) - i; // 右边节点数量 if (m >= 2) { res += cal(i, m - 1) * cal(j, m - 2) % MOD; res += cal(i, m - 2) * cal(j, m - 1) % MOD; } res += cal(i, m - 1) * cal(j, m - 1) % MOD; res %= MOD; } return f[n][m] = res; } // 求 n 个点的 AVL 树有多少种 int book[MAXN + 5]; int work(int n) { if (book[n]) return book[n]; int res = 0; int pre = 0; for (int i = 1; i <= n; i++) { int now = cal(n, i); res += now; res %= MOD; if (pre && !now) break; pre = now; } return book[n] = res; } signed main() { ios::sync_with_stdio(false); cin.tie(0); int n; while (cin >> n) cout << work(n) << "\n"; return 0; }
- 1