题解 P2767 【树的数量】

· · 题解

好像没什么人用更数学一点的方法解决这个问题……

考虑生成函数，首先要有一个节点，其次每个子树可以为空或者为 m 叉树，因此可列出式子

f(z) = z(1 + f(z))^m

变式为

z = \frac{f(z)}{(1 + f(z))^m}

那么定义逆函数

g(w) = \frac{w}{(1+w)^m}

根据 Lagrange 反演，有

[z^n]f(z) = \frac1n[w^{n-1}]\left(\frac w{g(w)}\right)^n

展开，用二项式定理可以得到

\frac{\binom{nm}{n - 1}}{n}

那么就算出组合数就完事了。

#include <cstdio>

using namespace std;

const int P = 10007;

int inv[P], fac[P], ifac[P];

int binom(int n, int m) {
    if (m > n)
        return 0;
    return fac[n] * ifac[m] % P * ifac[n - m] % P;
}

int lucas(int n, int m) {
    if (m > n)
        return 0;
    if (m == 0)
        return 1;
    return binom(n % P, m % P) * lucas(n / P, m / P) % P;
}

int main() {

    inv[1] = 1;
    for (int x = 2; x < P; ++x)
        inv[x] = -(P / x) * inv[P % x] % P + P;
    fac[0] = ifac[0] = 1;
    for (int x = 1; x < P; ++x) {
        fac[x] = fac[x - 1] * x % P;
        ifac[x] = ifac[x - 1] * inv[x] % P;
    }
    int n, m;
    scanf("%d%d", &n, &m);
    printf("%d\n", lucas(n * m, n - 1) * inv[n] % P);

    return 0;
}