Description

有一个$1\dots N$的排列$p_{1\dots N}$，定义这个排列的权值为其建出笛卡尔树后所有节点的权值之和，定义一个节点的权值为，如果这个节点有两个儿子$p_a, p_b$，则为$b-a$，否则为$0$。求所有可能排列的权值之和。

Solution

设$f_i$为$N=i$时的答案，枚举当前节点在原排列中的位置转移即可，转移方程为$$g_{i}=\sum \limits_{j=1}^i{i-1\choose j-1}\cdot(j-1)!\cdot (i-j)!\cdot j \f_{i}=2\cdot f_{i-1}+\\sum \limits_{j=1}^{i-1}\left({i-1\choose j-1}\cdot \left((i-j)!(g_{j-1}+f_{j-1})+(j-1)!(g_{i-j}+f_{i-j})\right)\right)$$

#include <iostream>
#include <cstdio>
#include <cstring>

class BearPermutations2{
private:
    int f[110], g[110], C[110][110], fac[110];
public:
    int getSum(int N, int MOD){
    	memset(f, 0, sizeof(f));
    	memset(g, 0, sizeof(g));
        fac[0]=1;
        for(int i=1; i<=N; i++) fac[i]=1ll*fac[i-1]*i%MOD;
        for(int i=0; i<=N; i++){
            C[i][0]=1;
            for(int j=1; j<=i; j++)
                C[i][j]=(C[i-1][j]+C[i-1][j-1])%MOD;
        }
        for(int i=1; i<=N; i++)
            for(int j=1; j<=i; j++)
                g[i]=(g[i]+1ll*C[i-1][j-1]*fac[j-1]%MOD*fac[i-j]%MOD*j%MOD)%MOD;
        for(int i=2; i<=N; i++){
            f[i]=2ll*f[i-1]%MOD;
            for(int j=2; j<i; j++){
                int tmp=0;
                tmp=(tmp+1ll*fac[j-1]*g[i-j]%MOD)%MOD;
                tmp=(tmp+1ll*fac[j-1]*f[i-j]%MOD)%MOD;
                tmp=(tmp+1ll*fac[i-j]*g[j-1]%MOD)%MOD;
                tmp=(tmp+1ll*fac[i-j]*f[j-1]%MOD)%MOD;
                tmp=1ll*C[i-1][j-1]*tmp%MOD;
                f[i]=(f[i]+tmp)%MOD;
            }
        }
        return f[N];
    }
};