prufer 序列 + 多项式重工业。
题意:求有多少棵大小为 的有根树满足最大度数为 。,。
最大点度数为 ,显然可以转化为最大点度数 减去最大点度数 的方案数。下面仅计算 的情况。
树的计数的常用两个手段是 Matrix-Tree 矩阵树定理和 prufer 序列。考虑使用 prufer 序列计算。由于度数等于出现次数 +1,于是我们只需要限定每一个点的出现次数 即可。
由于是同一个点出现多次只算一种方案,考虑使用 EGF,然后直接计算他的 次方即可。直接使用倍增快速幂即可通过,似乎没必要使用什么 的方法。
时间复杂度 或 。并不卡常。
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 ...