自动搬运

查看原文

来自洛谷，原作者为

	Elegia irony

搬运于2025-08-24 21:41:23，当前版本为作者最后更新于2018-09-23 21:39:34，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

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

考虑生成函数，首先要有一个节点，其次每个子树可以为空或者为 $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;
}