题解 SP1480 【PT07D - Let us count 1 2 3】
eee_hoho
2020-10-12 21:57:50
树计数四合一
对于前两问可以直接用Cayley来做。
Cayley说的就是$n$个点的带标号无根树的方案数是$n^{n-2}$。
那么有根树的方案数是$n^{n-1}$
考虑证明，先从有根树入手，假设当前有$k$个子树，那么我们可以任选一棵子树上的一个点连边到另一棵子树，那么方案数就是$n(k-1)$。
假设刚开始的$n$个点是$n$个子树，而每次操作会使子树减少一个，那么方案数为$\prod_{i=1}^{n-1}ni=n^{n-1}(n-1)!$。
而实际上我们连边的顺序是不需要考虑的，需要除上$(n-1)!$，所以最终方案数为$n^{n-1}$。
然后考虑后两问，变得比较困难。
我们注意$EGF$Exp的组合意义，$exp(F(x))=\sum_{i\ge1} \frac{F^i(x)}{i!}$，就是将$n$个有标号数放进若干个非空集合的方案数。
那么变换到无标号，那么有$Euler$变换如下：
$$\mathcal{E}(F(x))=\prod_{i\ge1}(\frac{1}{1-x^i})^{f_i}$$
然后我们回去第三问，如果你选择一个点当根，那么剩下的子树之间没有关联，就类似于刚才那个无标号计数。
那么设$f_n$表示$n$个点时无标号有根树的方案数，$F(x)$是$f$对应的生成函数，那么有：
$$F(x)=x\mathcal{E}(F(x))=x\prod_{i\ge1}(\frac{1}{1-x^i})^{f_i}$$
把$\prod(\frac{1}{1-x^i})^{f_i}$提出来做ln可以得到：
$$ln(\prod_{i\ge1}(\frac{1}{1-x^i})^{f_i})=\sum_{i\ge1}f_i\sum_{j\ge1}\frac{1}{j}x^{ij}=\sum_{j\ge1}\frac{1}{j}\sum_{i\ge1}f_i(x^j)^i=\sum_{i\ge1}\frac{1}{i}F(x^i)$$
再Exp回去代回原式有：
$$F(x)=xExp(\sum_{i\ge1}\frac{1}{i}F(x^i))$$
这个式子可以用牛顿迭代在$O(nlogn)$完成，但是这个题可以$O(n^2)$递推，于是我们继续化简。
两边求导有：
$$xF'(x)=F(x)+F(x)(\sum_{i\ge1}F'(x^i)x^i)$$
我们发现$(x^i)^k$才有值，那么考虑单独看第$n$项：
$$nf_n=f_n+\sum_{j=1}^nf_j\sum_{i=1}^nf_ii[i|n-j]$$
$$nf_n=f_n+\sum_{j=1}^nf_j\sum_{i|n-j}f_ii$$
那么设$g_n=\sum_{i|n}f_ii$，那么有：
$$f_n=\frac{\sum_{j=1}^nf_jg_{n-j}}{n-1}$$
这样子第三问就完成了。
然后第四问就完成了一半，我们考虑在有根树的基础上变为无根树，需要把一些重复的树减去，而如果我们统计的有根树的根都是重心，那么一定不会重复，所以可以拿第三问的答案$f_n$减去不是重心的方案数。
而如果一个根的子树大小超过了$\lfloor\frac{n}{2}\rfloor+1$，那么这个根肯定不是重心，方案数为$f_if_{n-i}$，于是答案为：
$$f_n-\sum_{i=\lfloor\frac{n}{2}\rfloor+1}^{n-1}f_if_{n-i}$$
而注意到$n$为偶数时会出现两个重心，所以还要减去$\begin{pmatrix}f_{\frac{n}{2}}\\2\end{pmatrix}$。
**Code**
``` cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
const int N = 1e3;
using namespace std;
int p,n,f[N + 5],g[N + 5],ans,inv[N + 5];
int mypow(int a,int x){int s = 1;for (;x;x & 1 ? s = 1ll * s * a % p : 0,a = 1ll * a * a % p,x >>= 1);return s;}
void solve1()
{
memset(f,0,sizeof(f));
memset(g,0,sizeof(g));
f[1] = 1;
g[1] = 1;
inv[1] = 1;
for (int i = 2;i <= n;i++)
inv[i] = 1ll * (p - p / i) * inv[p % i] % p;
for (int i = 2;i <= n;i++)
{
for (int j = 1;j <= i;j++)
f[i] += 1ll * f[j] * g[i - j] % p,f[i] %= p;
f[i] = 1ll * f[i] * inv[i - 1] % p;
for (int j = 1;j <= i;j++)
if (i % j == 0)
g[i] += 1ll * f[j] * j % p,g[i] %= p;
}
}
void solve2()
{
solve1();
int sm = 0;
for (int i = n / 2 + 1;i <= n - 1;i++)
sm += 1ll * f[i] * f[n - i] % p,sm %= p;
ans = (f[n] - sm) % p;
if (n % 2 == 0)
ans -= 1ll * f[n / 2] * (f[n / 2] - 1) / 2 % p,ans %= p;
}
int main()
{
int k;
while (scanf("%d%d%d",&k,&n,&p) != EOF)
{
if (k == 1)
printf("%d\n",mypow(n,max(0,n - 2)));
else
if (k == 2)
printf("%d\n",mypow(n,n - 1));
else
if (k == 3)
{
solve1();
printf("%d\n",(f[n] + p) % p);
}
else
{
solve2();
printf("%d\n",(ans + p) % p);
}
}
return 0;
}
```