气笑了

发现对于一个有$x$个节点的二叉树，有$x$个位置可以放。因此总共的二叉树的数量就是$n!$

将问题转化成，所有二叉树复杂度之和。 思考对于一颗确定的树，复杂度怎么算？ 记$cnt_i$为大小为$i$的子树个数，则复杂度为：

$\displaystyle\sum\limits_{i=1}^n (n-i)*i*cnt_i$

所以我们从$cnt_i$的角度考虑，记$f_{i,j}$为放了$i$个点的所有情况中，大小为$j$的子树个数之和。

转移式子见代码。

#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define F first
#define S second
#define mkp make_pair 
using namespace std;
int n,P;
int f[2010],nxt[2010],jc[2010]; 
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
//	freopen("ex.in","r",stdin);
//	freopen("my.out","w",stdout);
//	system("fc ex.out my.out");return 0;
	f[1]=1;cin>>n>>P;jc[0]=1;
	for(int i=1;i<=2000;i++)jc[i]=jc[i-1]*i%P;
	for(int i=2;i<=n;i++){
		for(int j=1;j<=i;j++){
			nxt[j]=f[j]*i%P;
		}nxt[1]=(nxt[1]+jc[i])%P;
		for(int j=1;j<=i-1;j++){
			nxt[j+1]=(nxt[j+1]+(j+1)*f[j])%P;
			nxt[j]=(nxt[j]-(j+1)*f[j]%P+P)%P;
		}for(int j=1;j<=i;j++){
			f[j]=nxt[j];nxt[j]=0;
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		ans=ans+(n-i)*i%P*f[i];
		ans%=P;
	}cout<<ans;
	return 0;
}

洛谷P4492 [HAOI2018] 苹果树

首先这个题可以想到画n笔可以构成的二叉树有n!种情况

原式就可以变形为求复杂度的和

然后对于算

树上所有结点对之间的最短距离之和通常是转换为边的经过次数

然后就差不多做完了

code

#include <bits/stdc++.h>
using namespace std;

const long long N = 2010;

long long n, p;

long long fac[N];

long long c[N][N];

int main(){
	cin >> n >> p;
	fac[0] = 1;
	for(long long i = 1;i <= n; i++){
		fac[i] = fac[i-1] * i % p;
	}
	c[0][0] = 1;
	for(long long i = 1;i <= n; i++){
		c[i][0] = c[i][i] = 1;
		for(long long j = 1;j < i; j++){
			c[i][j] = (c[i-1][j] + c[i-1][j-1]) % p;
		}
	}
	long long ans = 0;
	for(long long i = 2;i <= n; i++){
		for(long long j = 1;j <= n - i + 1; j++){
			ans = (ans + j * (n - j) % p * c[n-i][j-1] % p * fac[j] % p * fac[n-j-1] % p * i % p * (i - 1) % p) % p;
		}
	}
	cout << ans;
	return 0;
}