[Luogu4492]

一种常规写法

另一种还没看的写法

路径长的期望又乘上 \(n!\) , 因为\(n\)个点的二叉树有\(n!\)种,所以相当于算可能的情况的贡献和.

令 \(f_i\)表示 \(i\) 个节点的子树，根的深度为 \(1\) 时，所有点的期望深度之和（乘 \(i!\) ）的值

令 \(g_i\)表示 \(i\) 个节点的子树，期望两两路径之和（乘 \(i!\) ）的值

\(L,R\) 分别表示左右子树的大小

那么$ f_i = i * i! + \sum \limits_{L+R=i-1} \binom{i - 1}{L} (f_L * R! + f_R * L!)$

\(g_i = \sum \limits_{L+R=i-1} \binom{i - 1}{L} (g_L * R! + g_R * L! + f_L * (R + 1) * R! + f_R * (L + 1)* L!)\)

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define Debug(x) cout<<#x<<"="<<x<<endl
using namespace std;
typedef long long LL;
const int INF=1e9+7;
inline LL read(){
    register LL x=0,f=1;register char c=getchar();
    while(c<48||c>57){if(c=='-')f=-1;c=getchar();}
    while(c>=48&&c<=57)x=(x<<3)+(x<<1)+(c&15),c=getchar();
    return f*x;
}

const int MAXN=2005;

int f[MAXN],g[MAXN],C[MAXN][MAXN],fac[MAXN];
int n,mod;

inline int add(int x,int y){x+=y;return x>mod?x-mod:x;}
inline int mul(LL x,int y){x*=y;return x>mod?x%mod:x;}

int main(){
    n=read(),mod=read();
    for(int i=0;i<=n;i++) C[i][0]=1;
    fac[0]=1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++)
            C[i][j]=add(C[i-1][j],C[i-1][j-1]);
        fac[i]=mul(fac[i-1],i);
    }
    f[1]=1,g[1]=0;
    for(int i=2;i<=n;i++){
        f[i]=mul(i,fac[i]);
        for(int l=0;l<=i-1;l++){
            int r=i-1-l;
            f[i]=add(f[i],mul(C[i-1][l],add(mul(f[l],fac[r]),mul(f[r],fac[l]))));
            g[i]=add(g[i],mul(C[i-1][l],(1ll*g[l]*fac[r]%mod+1ll*g[r]*fac[l]%mod+1ll*f[l]*fac[r]%mod*(r+1)%mod+1ll*f[r]*fac[l]%mod*(l+1)%mod)%mod));
        }
    }
    printf("%d\n",g[n]);
}