[HAOI2018]苹果树（组合数学）

首先有个很奇妙而且很有用的性质：每个二叉树对应唯一的中序遍历，然后每个二叉树出现概率相同。所以n个节点的二叉树形态是n!种（题目中说了*n!已经是提示了），对每种方案求和即可得到期望。令f[i]表示i个节点的子树，根深度为1时，所有点的期望深度之和乘i!的值，令g[i]表示i个节点的子树，期望两两路径之和乘i!的值。

然后得到f[i]=i*i!+ΣC(i-1,L)(f[L]*R!+f[R]*L!)，g[i]=ΣC(i-1,L)(g[L]*R!+g[R]*L!+f[L]*R!*(R+1)+f[R]*L!*(L+1))，其中0<=L<i，L、R为左/右子树大小，只需要枚举L即可（因为R=i-1-L），复杂度O(n²)

这题这么水的吗qwq？其实当模数做NTT时，貌似可以分治NTT优化O(nlog²n)，反正我不会就不管了。

#include<bits/stdc++.h>

using namespace std;

const int N=;

int n,mod,c[N][N],fac[N],f[N],g[N];

int main()

{

    scanf("%d%d",&n,&mod);

    fac[]=c[][]=;

    for(int i=;i<=n;i++)

    {

        c[i][]=,fac[i]=1ll*fac[i-]*i%mod;

        for(int j=;j<=i;j++)c[i][j]=(c[i-][j-]+c[i-][j])%mod;

    }

    f[]=;

    for(int i=;i<=n;i++)

    {

        for(int L=;L<i;L++)

        {

            int R=i--L,F,G;

            F=(1ll*f[L]*fac[R]+1ll*f[R]*fac[L])%mod;

            G=(1ll*f[L]*fac[R]%mod*(R+)+1ll*f[R]*fac[L]%mod*(L+)+1ll*g[L]*fac[R]+1ll*g[R]*fac[L])%mod;

            f[i]=(f[i]+1ll*F*c[i-][L])%mod;

            g[i]=(g[i]+1ll*G*c[i-][L])%mod;

        }

        f[i]=(f[i]+1ll*i*fac[i])%mod;

    }

    printf("%d",g[n]);

}

巴特西

[HAOI2018]苹果树（组合数学）

最新文章

热门文章