目录
显示
题目链接
https://www.luogu.com.cn/problem/P4492
题解
首先易知一共有 \(n!\) 种形态的二叉树，所以我们实际上求的是所有二叉树不便度的总和。
计算每个点对之间的贡献似乎不太好办，我们考虑计算路径经过某条边的点对个数。
一个显然的事实是：假如切掉一条边 \(u \to v\)，将这棵树分为大小分别为 \(s\) 和 \(n-s\) 的两部分，则经过这条边的点对数为 \(2s(n-s)\)（\((u,v)\) 和 \((v,u)\) 算两次）。
现在我们按编号从小到大插入每一个点（点的插入顺序显然不影响结果）。
每插入一个点，我们枚举以这个点的子节点为根的子树大小 \(s\)。根据上面的叙述，可以知道，当前点和当前点的子节点之间的这条边，会对答案产生 \(2s(n-s)\) 的贡献。
假如我们现在正在插入第 \(i\) 个点，我们来考虑这几个事实：
- 对于前 \(i\) 个点，一共有 \(i!\) 种形态的二叉树；
- 从剩下的 \(n-i\) 个点中选 \(s\) 个点挂到 \(i\) 下面，一共有 \(C_{n-i}^s\) 种选法，再乘以 \(s!\) 的形态数，共有 \(s!C_{n-i}^s\) 种方案；
- 对于剩下的 \(n-i-s\) 个点，我们不能再挂到 \(i\) 下面了，第一个点有 \(i\) 种挂法，第二个点有 \(i+1\) 种挂法，以此类推，共有 \(\prod_{k=i}^{n-s-1}k\) 种挂法。
根据乘法原理，答案就是：
$$\sum_{i=1}^n \sum_{s=1}^{n-i} 2 \times s(n-s) \times i! \times s!C_{n-i}^s \prod_{k=i}^{n-s-1}k$$
\(p\) 不一定是质数，为了避开逆元不存在的问题，我们希望最终表达式里没有分母。
将组合数展开，约分后将两个阶乘相除写成若干个数连乘的形式，最后可以得到：
$$\sum_{i=1}^n 2 \times i!\sum_{s=1}^{n-i} s(n-s) \times \prod_{k=n-i-s+1}^{n-i}k \prod_{k=i}^{n-s-1}k$$
现在，我们可以预处理所有的 \(\prod_{k=l}^r k\) 来计算上面这个式子。
总时间复杂度 \(O(n^2)\)。
#include <iostream>
using namespace std;
long long a[2005][2005];
int main()
{
int n,p;
cin>>n>>p;
for(int i=1;i<=n;i++)
{
a[i][i]=i;
for(int j=0;j<i;j++)
a[i][j]=1;
for(int j=i+1;j<=n;j++)
a[i][j]=a[i][j-1]*j%p;
}
long long ans=0;
for(int i=1;i<=n;i++)
{
long long res=0;
for(int s=1;s<=n-i;s++)
res=(res+(n-s)*s%p*a[n-i-s+1][n-i]%p*a[i][n-s-1]%p)%p;
ans=(ans+2*res*a[1][i])%p;
}
cout<<ans<<endl;
return 0;
}