P2767 树的数量
拉格朗日反演：
$$
F(G(x)) = x \Longrightarrow [x ^ n]G(x) = \frac 1 n [x ^ {n - 1}] (\frac x {F(x)}) ^ n
$$
$ans _ i$ 表示有 $i$ 个节点的答案，考虑生成函数 $F(x) = \sum _ {i = 1} ans _ i x ^ i$ 。$n$ 个节点$m$ 叉树本质是 $m$ 个函数卷积，使得 $\sum _ {i = 1} ^ m s _ i = n - 1$ ，其中 $s _ i$ 表示节点个数。如果一个叉为 $0$ 也算一种方案，即 $(1 + F(x)) ^ m$ ，这是 $n - 1$ 的生成函数，再乘一个 $x$ 即为 $F(x)$ 。
$$
F(x) = x(1 + F(x)) ^ m
$$
那么
$$
x = \frac {F(x)} {(1 + F(x)) ^ m}
$$
构造函数
$$
G(x) = \frac x {(1 + x) ^ m}
$$
那么
$$
x = G(F(x))
$$ 。
上拉格朗日反演，有
$$
\begin {aligned}
[x ^ n] F(x) &= \frac 1 n [x ^ {n - 1}](\frac x {g(x)}) ^ n\\
& = \frac 1 n [x ^ {n - 1}]((1 + x) ^ m) ^ n\\
& = \frac 1 n [x ^ {n - 1}]\sum _ {k = 0} ^ {nm} \binom {nm} k x ^ k
\end {aligned}
$$
故答案为 $\frac {\binom {nm} {n - 1}} n$ 。
查看代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| #include <cstdio>
using namespace std;
template <class Type>
void read (Type &x)
{
char c;
bool flag = false;
while ((c = getchar()) < '0' || c > '9')
flag |= c == '-';
x = c - '0';
while ((c = getchar()) >= '0' && c <= '9')
x = (x << 3) + (x << 1) + c - '0';
if (flag) x = ~x + 1;
}
template <class Type, class ...Rest>
void read (Type &x, Rest &...y) { read(x); read(y...); }
template <class Type>
void write (Type x)
{
if (x < 0) putchar('-'), x = ~x + 1;
if (x > 9) write(x / 10);
putchar('0' + x % 10);
}
typedef long long LL;
const int N = 1e4 + 7;
int n, m, inv[N], fact[N], ifact[N];
void init ()
{
inv[1] = 1;
for (int i = 2; i < N; ++i)
inv[i] = -(LL)(N / i) * inv[N % i] % N;
fact[0] = ifact[0] = 1;
for (int i = 1; i < N; ++i)
{
fact[i] = (LL)fact[i - 1] * i % N;
ifact[i] = (LL)ifact[i - 1] * inv[i] % N;
}
}
int C (int a, int b) { return a < b ? 0 : (LL)fact[a] * ifact[b] % N * ifact[a - b] % N; }
int lucas (int a, int b) { return a | b ? (LL)lucas(a / N, b / N) * C(a % N, b % N) % N : 1; }
int main ()
{
init();
read(n, m);
write(((LL)lucas(n * m, n - 1) * inv[n] % N + N) % N);
return 0;
}
|