考虑枚举每一个iii,以及它的子树大小jjj
显然对于iii和他父亲的边的贡献就是j∗(n−j)j*(n-j)j∗(n−j) 考虑一个大小为nnn的二叉树,它所有可能的形态有n!n!n!种 那么对于点iii,这时整棵树形态有i!i!i!种那么大小为jjj的树的方案数就是之后n−in-in−i个点种填入j−1j-1j−1个点的可能乘上这个二叉树所有的形态,即Cj−1n−i∗j!C_{j-1}^{n-i}*j!Cj−1n−i∗j!
考虑对于剩下的n−j−i+1n-j-i+1n−j−i+1个点,第一个点可以插入i−1i-1i−1个点,第二个可以插入iii个点……,那么最后一个点就可以插入n−j−1n-j-1n−j−1个点
乘起来也就是(n−j−1)!(i−2)!\frac{(n-j-1)!}{(i-2)!}(i−2)!(n−j−1)!那么把所有乘起来ans=∑i=2n∑j=1n−i+1j∗(n−j)∗Cj−1n−i∗j!∗(n−j−1)!(i−2)!ans=\sum_{i=2}^{n}\sum_{j=1}^{n-i+1}j*(n-j)*C_{j-1}^{n-i}*j!*\frac{(n-j-1)!}{(i-2)!}ans=i=2∑nj=1∑n−i+1j∗(n−j)∗Cj−1n−i∗j!∗(i−2)!(n−j−1)!
=∑i=2n∑j=1n−i+1j∗j!∗Cj−1n−i∗(n−j)!∗i∗(i−1)=\sum_{i=2}^{n}\sum_{j=1}^{n-i+1}j*j!*C_{j-1}^{n-i}*(n-j)!*i*(i-1)=i=2∑nj=1∑n−i+1j∗j!∗Cj−1n−i∗(n−j)!∗i∗(i−1)n2n^2n2暴力枚举i,ji,ji,j就可以了
#includeusing namespace std;#define ll long long#define int long longinline int read(){ char ch=getchar(); int res=0,f=1; while(!isdigit(ch)){ if(ch=='-')f=-f;ch=getchar();} while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=getchar(); return res*f;}const int N=2005;int n,mod,fac[N],c[N][N];ll ans=0;signed main(){ n=read(),mod=read(); c[0][0]=1; for(int i=1;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; } } fac[0]=1; for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i%mod; for(int i=2;i<=n;i++){ for(int j=1;j<=n-i+1;j++){ ans=(ans+1ll*j*c[n-i][j-1]%mod*fac[j]%mod*fac[n-j]%mod*i%mod*(i-1)%mod)%mod; } } cout<