BZOJ5305 [Haoi2018]苹果树

可以发现一个\(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);
}