[ZJOI2018] 树

· · 题解

对于一棵无标号有根树 T，定义 f(T) 表示给它的点标号的本质不同合法方案数。

题目要我们求的就是

\dfrac{1}{((n-1)!)^m}\sum\limits_{|T|=n}f^m(T)

先考虑给定 T，如何求 f(T)。可以得到

f(T)=|T|!\prod\limits_{u\in T}\dfrac{1}{size_u}\prod\limits\dfrac{1}{w_{u,i}!}

其中 w_{u,i} 的意义是：考虑所有以 u 的某一个儿子为根的子树，把所有互相同构子树的划分入同一个等价类，第 i 个等价类的大小。

考虑 dp。

令

dp_i=\sum\limits_{|T|=i}f^m(T)

但是推一推就会发现完全无法转移。

先利用生成函数表示 dp_i：

dp_i=\dfrac{1}{i^m}[x^{i-1}]\prod\limits_j\prod\limits_{|T|=j}\sum\limits_{k=0}^{\infty}\dfrac{f^{km}(T)}{(k!)^m}x^{jk}

这一步其实非常不自然，而且后面也不是很容易，所以挺难想到的。

然后是一个套路：

令

A_i=\prod\limits_{|T|=i}\sum\limits_{k=0}^{\infty}\dfrac{f^{km}(T)}{(k!)^m}x^{ik}

则

=\exp(\sum\limits_{|T|=i}\ln(\sum\limits_{k=0}^{\infty}\dfrac{(f^m(T)x^i)^k}{(k!)^m}))

令

B=\ln(\sum\limits_{k=0}^{\infty}\dfrac{x^k}{(k!)^m})

则

A_i=\exp(\sum\limits_{|T|=i}\sum\limits_{k=0}^{\infty}([x^k]B)f^{km}(T)x^{ik}) =\exp(\sum\limits_{k=0}^{\infty}([x^k]B)\sum\limits_{|T|=i}f^{km}(T)x^{ik})

此时我们发现 A_i 的柿子中有一个与 dp_i 很类似的东西：

\sum\limits_{|T|=i}f^{km}(T)

为了处理这个东西，我们可以改变一下 dp 的定义，同时也需要改变一些其它的定义。

令

dp_{i,t}=\sum\limits_{|T|=i}f^{tm}(T) A_{i,t}=\prod\limits_{|T|=i}\sum\limits_{k=0}^{\infty}\dfrac{f^{tkm}(T)}{(k!)^{tm}}x^{ik} B_t=\ln(\sum\limits_{k=0}^{\infty}\dfrac{x^k}{(k!)^{tm}})

则

dp_{i,t}=\dfrac{1}{i^{tm}}[x^{i-1}]\prod\limits_j\prod\limits_{|T|=j}\sum\limits_{k=0}^{\infty}\dfrac{f^{tkm}(T)}{(k!)^{tm}}x^{jk} =\dfrac{1}{i^{tm}}[x^{i-1}]\prod\limits_jA_{j,t} =\dfrac{1}{i^{tm}}[x^{i-1}]\prod\limits_j\exp(\sum\limits_{k=0}^{\infty}([x^k]B_t)\sum\limits_{|T|=j}f^{tkm}(T)x^{jk}) =\dfrac{1}{i^{tm}}[x^{i-1}]\prod\limits_j\exp(\sum\limits_{k=0}^{\infty}([x^k]B_t)dp_{j,tk}x^{jk})

我们只需要知道 dp_{n,1} 的值即可。

推到这里，我们就已经得到了一个多项式复杂度做法了！

观察可得，dp_{i,t} 中只需要保留 t\le\dfrac{n}{i} 的部分。换言之，只需要保留 i\le\dfrac{n}{t} 的部分。

进一步推得 B_t 只需要保留次数 \le\dfrac{n}{t} 的项。

求出 B_t 需要进行一次多项式 \ln，暴力完成的复杂度为 O(\dfrac{n^2}{t^2})。因此这一部分复杂度为

O(\sum\limits\dfrac{n^2}{t^2})=O(n^2)

预处理完 B_t 后我们还需要进行 dp。

从小到大枚举 i，只有满足 i'<i 的 dp_{i',*} 会对 dp_{i,*} 产生贡献。

计算 dp_{i,*} 的时候，我们需要维护 \dfrac{n}{i} 个多项式

C_t=\prod\limits_j\exp(\sum\limits_{k=0}^{\infty}([x^k]B_t)dp_{j,tk}x^{jk})

可以根据之前的柿子快速求出 dp_{i,*}，然后更新 C_t。

C_t\leftarrow C_t\exp(\sum\limits_{k=0}^{\infty}([x^k]B_t)dp_{i,tk}x^{ik})

同时，根据之前的观察，C_t 也只需要保留次数 \le\dfrac{n}{t} 的项。

这些操作都可以暴力完成。

对于每一对 (i,t)，我们都要进行一次多项式 \exp 和 \dfrac{n}{i} 次卷积，暴力完成的复杂度分别为 O(\dfrac{n^2}{i^2t^2}) 和 O(\dfrac{n^2}{it^2})。因此这一部分的复杂度为

O(\sum\limits_i\sum\limits_t(\dfrac{n^2}{i^2t^2}+\dfrac{n^2}{it^2}))=O(n^2\log n)

多项式 \ln 和 \exp 都不在瓶颈上。

时间复杂度 O(n^2\log n)。

参考代码（变量名与题解中有很大不同，请谨慎食用）：

#include <bits/stdc++.h>
using namespace std;
#define N 2005
int n,m,MOD,fc[N],A[N],B[N],w[N][N],z[N][N],dp[N][N];
int add(int x,int y) {x+=y;return x<MOD?x:x-MOD;}
void W(int &x,int y) {x+=y;if(x>=MOD) x-=MOD;}
int qPow(int x,int y)
{
    int res=1;
    for(;y;y/=2,x=1ll*x*x%MOD) if(y&1) res=1ll*res*x%MOD;return res;
}
void polyLn(int n,int a[],int res[])
{
    for(int i=0;i<=n;++i) res[i]=0;
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<i;++j) W(res[i],1ll*a[i-j]*res[j]%MOD*j%MOD);
        res[i]=add(a[i],MOD-1ll*res[i]*qPow(i,MOD-2)%MOD);
    }
}
void polyExp(int n,int a[],int res[])
{
    res[0]=1;for(int i=1;i<=n;++i) res[i]=0;
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=i;++j) W(res[i],1ll*a[j]*res[i-j]%MOD*j%MOD);
        res[i]=1ll*res[i]*qPow(i,MOD-2)%MOD;
    }
}
int main()
{
    scanf("%d %d %d",&n,&m,&MOD);fc[0]=1;
    for(int i=1;i<=n;++i) fc[i]=1ll*fc[i-1]*i%MOD;
    for(int i=1;i<=n;++i)
    {
        for(int j=0;j<=n/i;++j) A[j]=qPow(fc[j],MOD-1ll*i*m%(MOD-1)-1);
        polyLn(n/i,A,w[i]);
    }for(int i=1;i<=n;++i) z[i][0]=1;
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=n/i;++j)
            dp[i][j]=1ll*z[j][i-1]*qPow(i,MOD-1ll*j*m%(MOD-1)-1)%MOD;
        for(int j=1;j<=n/i;++j)
        {
            for(int k=0;k<=n/i/j;++k) B[k]=1ll*w[j][k]*dp[i][j*k]%MOD;
            polyExp(n/i/j,B,A);
            for(int k=n/j;k>=0;--k) for(int l=1;l<=(n/j-k)/i;++l)
                W(z[j][k+i*l],1ll*z[j][k]*A[l]%MOD);
        }
    }printf("%lld\n",1ll*dp[n][1]*qPow(n,m)%MOD);return 0;
}