T4 Uniformly Branched Trees (CF724F)

· · 个人记录

T4 Uniformly Branched Trees (CF724F)

人生中第二道黑题

又一道计数题，但相比T3要好理解得多

细节还是一如既往的多

CF传送门

洛谷传送门

题意简述

求有多少种不同构（即交换节点不能使两棵树完全相同）的 n 个点构成的树，满足除了子节点（度数为1的结点）外，其余结点的度数均为 d 。答案对质数 mod 取模。

数据范围
1 \leq n \leq 10^3 2 \leq d \leq 10 10^8 \leq mod \leq 10^9
题解

思路

刚拿到这个题目，显然最大的障碍就是如何处理同构（或者说如何判重）

对于一颗无根树来说判重显然是不现实的

自然就找一个根咯

这个根可不能随便乱找，要有一些有用的性质才行

比如说重心

这样一来子树的大小就不会超过 \frac {n}{2} 了

那接下来怎么做呢？

当然不是树形dp因为连一颗固定的树都没有

但还是得dp

关联的状态是什么呢？

显然有 节点个数，子树大小的上限

还有一个很妙的，根节点的子树个数

这样就方便转移了

于是用 f[i][j][k] 表示 有i个节点，根节点有j个子节点，子树大小均不超过k的方案总数

一种是所有子树 **（指根节点的子树，下同）** 大小连等于 $k$ 都没有，全都比 $k$ 小 直接转移就行了 $f[i][j][k]+=f[i][j][k-1]

第二种则是有子树大小为 k 的

假设有 t 棵子树大小为 k 的

那去掉这 t 棵，其实就是 f[i-t*j][j-t][k-1]

但从 f[i-t*j][j-t][k-1] 加上这些子树的时候，其实又有很多种方案

每颗子树有 f[t][d-1][k-1] 种

其实就是t棵子树中，每颗子树都可不分顺序地，可重复地选 f[t][d-1][k-1] 种方案，即

C^{2}_{f[t][d-1][k-1]+t-1}

所以状态转移方程就出来了（别忘了前面的）

f[i][j][k]+=f[i][j][k-1] f[i][j][k]+=f[i-t*j][j-t][k-1]+C^{2}_{f[t][d-1][k-1]+t-1} \times f[t][d-1][k-1]

最后，不要得意忘形o

还有双重心要考虑（即n为偶数）

可以想象一下，就是一座桥连接着两颗全等（对称）的树，桥的两头就是两个重心

大概是这样的

\    /
/\__/\
 /  \

怎么画得跟个人似的[doge]

两边的方案自然是完全一样的

f[n/2][d-1][n/2]

这时候就会发现一种重复了

比如有两个方案 a 和 b

左 a右 b 和 左 b 右 a ，是没有本质区别的（翻转一下就一样了）

当然 a!=b 不然是不会计算两次的

要是这样的话，直接减去 C^{2}_{f[n/2][d-1][n/2]}不就行啦~

做法

这个就很简单了

直接按 i，j，k，t 枚举转移即可

注意初始化还有枚举的区间（写在下面了QwQ）

组合数运算要除法，要用到逆元

只是阶乘的逆元，看到质数用费马小定理暴力处理就好了（反正不超过 d ）

AC代码

#include<bits/stdc++.h>
using namespace std;
const long long N=1005;
long long n,d,mod;
long long f[N][11][N/2];
long long inv[11];
long long ksm(long long a,long long x){
    long long ans=1;
    while(x){
        if(x%2==1) ans=ans*a%mod;
        a=a*a%mod;
        x/=2;
    }
    return ans%mod;
}
void pre(){
    inv[0]=1;
    long long tmp=1;
    for(long long i=1;i<=d;i++){
        tmp=tmp*i;
        inv[i]=ksm(tmp,mod-2);
    }
}
long long C(long long m,long long n){
    long long ans=1;
    for(long long i=m;i>=m-n+1;i--) ans=(ans*i)%mod;
    ans=(ans*inv[n])%mod;
    return ans;
}
int main(){
    cin>>n>>d>>mod;
    if(n<=2) {cout<<1;return 0;}
    pre();
    for(long long i=0;i<=n/2;i++) f[1][0][i]=1;//初始化，只有一个节点就是1种情况 
    for(long long i=2;i<=n;i++){//枚举i 
        for(long long j=1;j<=min(i-1,d);j++){//枚举j
        //j<=i-1(每棵子树只有一个节点时最多也只有i-1棵子树)
        //j<=d(根节点至多有d棵子树) 
            for(long long k=1;k<=n/2;k++){
                f[i][j][k]=f[i][j][k-1];
                for(long long t=1;t<=min((i-1)/k,j);t++){
                    //i-t*k>0 => t<=(i-1)/k
                    //t<=j(放入的新子树数量t不会超过有的子树数量j) 
                    long long tmp=(k==1)?0:d-1;
                    //如果k=1，即只有一个根节点(无子树)，需要特判 
                    f[i][j][k]=(f[i][j][k]+f[i-t*k][j-t][k-1]*C(f[k][tmp][k-1]+t-1,t)%mod)%mod;
                }
            } 
        }
    }
    long long ans=f[n][d][n/2];
    if(n%2==0) ans=(ans+mod-C(f[n/2][d-1][n/2],2))%mod;//双重心特判 
    cout<<ans;
}