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];
}
};