https://scg3.piaoztsdy.cn/p/211
对于一棵 个结点的「平衡树」，枚举其根结点的子树个数 和子树大小 。
- 首先要将 这 个编号无序地分给 个互不区分的（稍后会根据每个子树中的最小结点编号加以区分），大小均为 的子树，方案数为 。
- 接下来，每棵（互相区分的）子树均有 种不同的结构（ 为大小等于 的本质不同的「平衡树」的数量），方案数为 。
因此我们得到了递推式：
根据初始状态 ，枚举 和 逐个更新答案即可。
最终的时间复杂度为 ，空间复杂度为 。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 12;
const int P = 1e9 + 7;
long long a[N], fc[N], ffc[N];
int divs(int a, int b = 1, int p = P)
{
if (b % a == 0) return b / a;
int x = divs(p % a, a - b % a, a);
return (1ll * x * p + b) / a;
}
int main()
{
freopen("trees.in", "r", stdin);
freopen("trees.out", "w", stdout);
int n;
cin >> n;
fc[0] = 1;
for (int i = 1; i <= n; i++)
fc[i] = fc[i - 1] * i % P;
ffc[n] = divs(fc[n]);
for (int i = n - 1; i >= 0; i--)
ffc[i] = ffc[i + 1] * (i + 1) % P;
a[1] = 1;
for (int y = 1; y <= n; y++)
{
a[y] = a[y] * ffc[y] % P;
long long cur = 1;
for (int x = y, z = 1; x <= n; x += y, z++)
{
cur = cur * a[y] % P;
long long val = fc[x] * ffc[z] % P;
a[x + 1] += cur * val % P;
if (a[x + 1] >= P) a[x + 1] -= P;
}
}
int ans = 0;
for (int i = 1; i <= n; i++)
{
ans += a[i] * fc[i] % P;
if (ans >= P) ans -= P;
}
cout << ans << endl;
return 0;
}
暂无评论