BZOJ5305: [Haoi2018]苹果树

https://lydsy.com/JudgeOnline/problem.php?id=5305

分析:

需要推一推式子的题。
枚举(i)，考虑与父亲这条边的贡献。
枚举子树大小(j)，则贡献为(j(n-j))。
求方案数，子树内的方案数为(inom{n-i}{j-1}j!)
子树外的方案数:
先考虑(i)以上的部分(i!)，在向其中插入剩下的(n-i-j+1)个点。
插第一个点有(i+1)种方案，插最后一个点有(n+j-1)种方案。
这部分贡献即(frac{(n+j-1)!}{i!})
整理可得式子，见代码。

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
using namespace std;
typedef long long ll;
#define N 2050
int mod,n;
ll C[N][N],fac[N];
int main() {
	scanf("%d%d",&n,&mod);
	int i,j;
	for(i=0;i<=n;i++) {
		C[i][0]=1;
		for(j=1;j<=i;j++) {
			C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
		}
	}
	for(fac[0]=i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod;
	ll ans=0;
	for(i=2;i<=n;i++) {
		for(j=1;j<=n-i+1;j++) {
			ans=(ans+j*(n-j)*C[n-i][j-1]%mod*fac[j]%mod*i*(i-1)%mod*fac[n-j-1])%mod;
		}
	}
	printf("%lld
",(ans+mod)%mod);
}