P4492 [HAOI2018]苹果树

除了神仙啥都不想说了orz->这里

首先生成二叉树的时候,第一个点有(1)种选法,第二个点有(2)种选法...第(n)个点有(n)种选法,于是树的形态共有(n!)种,需要求它们总共的点对距离和

发现按点来考虑太麻烦了,我们按边来考虑贡献,对(i)的父亲边来说,有(sz_i(n-sz_i))个点对会经过这一条边,所以这一条边对答案就有这么多的贡献

于是考虑一下(O(n^2))的枚举,设(sz_i)为子树的大小,(i)为当前点,那么这棵子树的形态有(sz_i!)种,子树的编号有(C_{n-i}^{sz_i-1})种(生成(i)之后从剩下的点中选出(sz_i-1)个让他们在(i)的子树里),于是总的方案数就是(sz_i!C_{n-i}^{sz_i-1})

然后考虑子树外的方案数,生成(i)之前共有(i!)种方法,而生成(i)之后的点不能放到(i)的子树中,于是后面的点有((i+1-2),(i+2-2),...(n-sz_i+1-2))种方法(因为放到(i)的子树中的点并不会影响外面的点的方案数),乘起来化简一下就是(i(i-1)(n-sz_i-1)!)种方法

于是最后的答案就是$$ans=sum_{i=2}^{n}sum_{j=1}^{n-i+1}j(n-j)j!C_{n-i}^{j-1}i(i-1)(n-j-1)!$$

//minamoto
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2005;
int n;ll mod,dp[N][N],C[N][N],fac[N],res;
int main(){
//	freopen("testdata.in","r",stdin);
	scanf("%d%lld",&n,&mod),fac[0]=1;
	for(int i=0;i<=n;++i)C[i][i]=C[0][i]=1;
	for(int i=0;i<=n;++i)for(int j=1;j<n;++j)C[j][i]=(C[j-1][i-1]+C[j][i-1])%mod;
	for(int i=1;i<=n;++i)fac[i]=fac[i-1]*i%mod;dp[1][1]=1;
	for(int i=2;i<=n;++i)for(int j=1;j<=n-i+1;++j)
	(res+=fac[j]*C[j-1][n-i]%mod*j*(n-j)%mod*fac[n-j-1]%mod*i%mod*(i-1)%mod)%=mod;
//	for(int i=2;i<=n;++i)for(int j=1;j<=i;++j)dp[i][j]=fac[i-2]*j%mod*(j-1)%mod;
//	for(int i=2;i<=n;++i)for(int j=1;j<=n-i+1;++j)
//	(res+=fac[j]*C[j-1][n-i]%mod*j*(n-j)%mod*dp[n-j+1][i])%=mod;
//	也可以这样打表预处理一下再算 
	printf("%lld
",res);return 0;
}
原文地址:https://www.cnblogs.com/bztMinamoto/p/9954040.html