题解：P5219 无聊的水题 I

· · 题解

如果你不会 FFT/NTT 等多项式算法，这篇题解可能会帮到你。

题意：求有 n 个节点，且节点的最大度数恰好为 m 的不同树的数量。

直接求最大度数恰好为 m 的树可能不太好求，根据差分的思想，答案等于最大度数 \le m 的树的数量 - 最大度数 \le m - 1 的树的数量，因此接下来只需要思考最大度数 \le p 的树的数量。

根据 Prufer 序列的性质，若节点 i 在树中的度数为 d_i，则其在 Prufer 序列中出现次数为 d_i - 1。最大度数 \le p，等价于在长度为 n - 2 的 Prufer 序列中，每个数字的出现次数不超过 k = p - 1。到此，问题被转化为了一个排列组合问题。

要从 n 个不同的数字中挑选元素组成长度为 n - 2 的序列，且每个数出现次数 \le k。\ 对于某一个单独的数字，其生成函数（EGF）为：

F(x) = \sum_{i = 0}^k \frac{x ^ i}{i!}

因为有 n 个独立的数字，所以整个序列的 EGF 就是

G(x) = (F(x)) ^ n

我们最终需要的合法 Prufer 序列的数量，就是 (n - 2)! \cdot [x ^ {n - 2}]G(x)，用多项式快速幂就做完了，时间复杂度 \mathcal{O}(n \log n)。

:::success[代码]

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using V = vector<LL>;
const int N = 2e5 + 5, M = 998244353;
LL n, m, r[N], f[N];
LL P(LL x, LL y) {
  LL s = 1;
  for (; y; x = x * x % M, y >>= 1) y & 1 && (s = s * x % M);
  return s;
}
void NTT(V &a, int p, int k) {
  for (int i = 0; i < k; i++) {
    i < r[i] && (swap(a[i], a[r[i]]), 1);
  }
  for (int d = 1; d < k; d <<= 1) {
    LL wn = P(~p ? 3 : (M + 1) / 3, (M - 1) / (d << 1));
    for (int i = 0; i < k; i += (d << 1)) {
      LL w = 1;
      for (int j = 0; j < d; j++, w = w * wn % M) {
        LL x = a[i + j], y = a[i + j + d];
        a[i + j] = (x + w * y % M) % M;
        a[i + j + d] = (x - w * y % M + M) % M;
      }
    }
  }
}
V X(V a, V b) {
  int n = a.size() - 1, m = b.size() - 1, k, l = 0;
  for (k = 1; k <= n + m; k *= 2, l++);
  for (int i = 0; i < k; i++) {
    r[i] = ((r[i >> 1] >> 1) | ((i & 1) << l - 1));
  }
  a.resize(k), b.resize(k);
  NTT(a, 1, k), NTT(b, 1, k);
  V c(k);
  for (int i = 0; i < k; i++) c[i] = a[i] * b[i] % M;
  NTT(c, -1, k);  
  for (LL &x : c) x = x * P(k, M - 2) % M;
  c.resize(::n - 1);
  return c;
}
V P(V x, LL y) {
  V s(1, 1);
  for (; y; x = X(x, x), y >>= 1) y & 1 && (s = X(s, x), 1);
  return s;
}
LL C(LL p) {
  LL k = p - 1, v = 1;
  V a;
  for (int i = 0; i <= k; i++) a.push_back(P(f[i], M - 2));
  return f[n - 2] * P(a, n)[n - 2] % M;
}
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> m;
  for (int i = f[0] = 1; i <= n; i++) f[i] = f[i - 1] * i % M;
  cout << (C(m) - C(m - 1) + M) % M;
  return 0;
}

:::

这里还有一种不用多项式算法的做法：

考虑对 G(x) = (F(x)) ^ n 两边同时求 \ln，有

\ln G(x) = n \cdot \ln F(x)

对两边同时求导，得到

\frac{G'(x)}{G(x)} = n \cdot \frac{F'(x)}{F(x)}

移个项，得到

G'(x) \cdot F(x) = n \cdot G(x) \cdot F'(x)

设 \displaystyle F(x) = \sum_{i = 0}^{k} f_i x ^ i，其中 \displaystyle f_i = \frac{1}{i!}，设 \displaystyle G(x) = \sum_{i = 0}^{\infty} g_i x ^ i。

对等式两边同时提取 x ^ {i - 1} 的系数：

两边系数必然相等，得到等式

i \cdot g_i - \sum_{j = 1}^{\min(i, k)} (i - j) f_j g_{i - j} = n \sum_{j = 1}^{\min(i, k)} j \cdot f_j g_{i - j}

整理可得

\displaystyle \frac 1 i \sum_{j = 0}^{\min(i, k)} (j (n + 1) - i) f_j g_{i - j} & i > 1 \\ 1 & i = 0 \end{cases}

预处理一下阶乘和逆元即可做到 \mathcal{O}(nk)，总时间复杂度 \mathcal{O}(nm)，在 6s 的时限下完全可以通过本题。

:::success[代码]

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 5e4 + 5, M = 998244353;
LL n, m, f[N], g[N];
LL P(LL x, LL y) {
  LL s = 1;
  for (; y; x = x * x % M, y >>= 1) y & 1 && (s = s * x % M);
  return s;
}
LL C(LL p) {
  LL k = p - 1, v = 1;
  for (LL i = g[0] = 1; i <= n - 2; i++) {
    g[i] = 0;
    for (LL j = 1; j <= min(i, k); j++) {
      g[i] = (g[i] + (j * (n + 1) - i + M) % M * f[j] % M * g[i - j] % M) % M;
    }
    g[i] = g[i] * P(i, M - 2) % M, v = v * i % M;
  }
  return v * g[n - 2] % M;
}
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> m;
  for (int i = f[0] = 1; i <= n; i++) f[i] = f[i - 1] * P(i, M - 2) % M;
  cout << (C(m) - C(m - 1) + M) % M;
  return 0;
}

:::

感谢 @apple365 老师的指导。