Luogu P5219 无聊的水题 I

prufer 序列 + 多项式重工业。

题意:求有多少棵大小为 n 的有根树满足最大度数为 mn5×104mn

最大点度数为 m,显然可以转化为最大点度数 m 减去最大点度数 m1 的方案数。下面仅计算 m 的情况。

树的计数的常用两个手段是 Matrix-Tree 矩阵树定理和 prufer 序列。考虑使用 prufer 序列计算。由于度数等于出现次数 +1,于是我们只需要限定每一个点的出现次数 <m 即可。

由于是同一个点出现多次只算一种方案,考虑使用 EGF,然后直接计算他的 n 次方即可。直接使用倍增快速幂即可通过,似乎没必要使用什么 ln/exp 的方法。

时间复杂度 O(nlog2n)O(nlogn)。并不卡常。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int solve(int lim)
{
if (lim <= 0) return 0;
poly bs(lim + 1, 1), res(1, 1);
for (int i = 0; i <= lim; ++ i) bs[i] = (LL) bs[i] * infact[i] % Mod;
int k = n;
for (; k; k >>= 1, bs = bs * bs, bs.resize(std::min((int) bs.size(), n - 1)))
if (k & 1) res = res * bs, res.resize(std::min((int) res.size(), n - 1));
return res[n - 2] * (LL) fact[n - 2] % Mod;
}

int main()
{
init();
int m, res;
std::cin >> n >> m;
printf("%d\n", adj(res = solve(m - 1) - solve(m - 2)));
return 0;
}

Gitalking ...