[组合数学][大组合数取模][TreeDp] UVA 1436 Counting heaps

题目链接

思路比较简单但是很经典的一题，最近一直在补数学。。

用dp(u)表示以节点u为根的种类数，则由基本的组合数学可以得出\[dp(u)=(\frac{(n-1)!}{\prod size(v)})*\prod dp(v),\ u\ is\ v’s\ parent\] 其中\[size(v)\]是以v为根的子树的大小。然后由于这里模值是任取的，所以不能用求逆元的方式来做，否则的话也太简单了。

考虑进一步化简这个式子，把\[dp(v)\] 们展开（脑海中展开）可以发现对于每个节点来说，他以 \[(size(v)-1)!\]的形式出现在分子上一次，以\[size(v)!\]的形式出现在分母上一次，所以最终把所有节点（不仅仅是root的直接儿子）全部代进去就可以得到\[dp(root)=(\frac{(n-1)!}{\prod_{v=2}^{v=n} size(v)})\]

题目有个坑点的话是dfs会爆栈然后返回wa，改成bfs就过了。

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
int mod=998244353;
const int maxn=5e5+10;

LL p[maxn],tot;
bool isp[maxn];
int n,m;

void eular(){
    LL tmp;
    for(int i=2;i<maxn;i++){
        if(isp[i]==0) p[++tot]=i;
        for(int j=1;j<=tot;j++){
            tmp=p[j]*i;
            if(tmp>=maxn) break;
            isp[tmp]=1;
            if(i%p[j]==0) break;
        }
    }
}



bool vis[maxn];
vector<int> G[maxn];
int gl[maxn],chs[maxn],fa[maxn],que[maxn],head,tail;
// int dfs1(int x){
//     chs[x]=1;
//     for(int i=0;i<gl[x];i++){
//         chs[x]+=dfs1(G[x][i]);
//     }
//     return chs[x];
// }

void bfs(){
    head=tail=0;
    que[tail++]=1;
    while(head!=tail){
        int cur=que[head++];
        chs[cur]=1;
        for(int i=0;i<gl[cur];i++){
            que[tail++]=G[cur][i];
        }
    }
    for(int i=tail-1;i;i--){
        chs[fa[que[i]]]+=chs[que[i]];
    }
}

int cnt[maxn];
int tt,op,mt;
void Div(LL A,int f){
    tt=0;
    for(LL i=1;p[i]*p[i]<=A&&(isp[A]);i++){
        if(A%p[i]==0){
            tt=p[i];
            while(A%p[i]==0){
                A/=p[i];
                cnt[tt]+=f;
            }
        }
    }
    if(A!=1){
        tt=A;
        cnt[A]+=f;
    }
    mt=max(mt,tt);
}

LL C(){
    for(int i=1;i<=n-1;i++)
        Div(i,1);
    for(int i=2;i<=n;i++)
        Div(chs[i],-1);
    LL res=1;
    for(int i=1;p[i]<=mt;i++){
        while(cnt[p[i]]){
            res*=p[i];
            if(res>=mod) res%=mod;
            cnt[p[i]]--;
        }
    }
    return res;
}

void init(){
    mt=tt=0;
    memset(cnt,0,sizeof(cnt));
}

int main(){
    eular();
    int t,v;
    scanf("%d",&t);
    while(t--){
        init();
        scanf("%d%d",&n,&m);
        mod=m;
        for(int i=1;i<=n;i++) G[i].clear(),gl[i]=0;
        for(int i=2;i<=n;i++){
            scanf("%d",&v);
            G[v].push_back(i);
            fa[i]=v;
        }
        for(int i=1;i<=n;i++) gl[i]=G[i].size();
        bfs();
        LL ans=C();

        printf("%lld\n",ans);
    }
    return 0;
}