大家好，又见面了，我是你们的朋友全栈君。
可以发现一个\(n\)节点的树的方案数是\(n!\)
因为对于第\(i\)个点有\(i\)种选择方式 可以归纳证明 第\(i\)个点选择一个位置之后又新加入了他的左右子树 即可选择位置变为\(i+1\)
那么我们对于一个点\(i\)枚举它的子树大小\(j\) 统计要经过他和父亲的连边的点对数
它的子树的方案数即为\(j!*C_{n-i}^{j-1}\)
子树外首先要先构造出大小为\(i\)的子树 方案数\(i!\)
之后我们再在外面这棵树上添加新节点 容易发现点\(i\)的子树不能再填充 相当于少了\(2\)个填充位置 于是对于剩下的\(n-i-j+1\)个点的方案数即为\(\sum_{k=1}^{n-i-j+1}(k+i-2)\)
当然对于每一种方案它的点对数都是\(j*(n-j)\)
将以上各式相乘并化简即得\(ans=\sum_{i=1}^{n}\sum_{j=1}^{n-i+1}(j! * (n-j)! * \binom{n-i}{j-1} * i * (i-1) * j)\)
#include<bits/stdc++.h>
using namespace std;
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define pa pair<int,int>
#define ll long long
#define mk make_pair
#define pb push_back
#define fi first
#define se second
#define cl(x) memset(x,0,sizeof x)
#ifdef Devil_Gary
#define bug(x) cout<<(#x)<<" "<<(x)<<endl
#define debug(...) fprintf(stderr, __VA_ARGS__)
#else
#define bug(x)
#define debug(...)
#endif
const int INF = 0x7fffffff;
const int N=2e3+5;
/*
char *TT,*mo,but[(1<<15)+2];
#define getchar() ((TT==mo&&(mo=(TT=but)+fread(but,1,1<<15,stdin),TT==mo))?-1:*TT++)//*/
inline int read(){
int x=0,rev=0,ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')rev=1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return rev?-x:x;
}
int n,mod,ans,fac[N],C[N][N];
void init(){
fac[0]=fac[1]=1;
for(int i=2;i<=n;i++) fac[i]=(ll)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-1]+C[i-1][j])%mod;
}
}
int calc(int a,int b){
return (ll)a*(a-1)*b%mod;
}
int main(){
#ifdef Devil_Gary
freopen("in.txt","r",stdin);
#endif
n=read(),mod=read(),init();
for(int i=2;i<=n;i++) for(int j=n-i+1;j;--j) (ans+=(ll)fac[j]*fac[n-j]%mod*C[n-i][j-1]%mod*calc(i,j)%mod)%=mod;//,bug(ans);
printf("%d\n",ans);
}转载于:https://www.cnblogs.com/devil-gary/p/9067329.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/107501.html原文链接：https://javaforall.net
