[洛谷 4492,loj 2526][HAOI2018]苹果树

题目链接

https://www.luogu.com.cn/problem/P4492

https://loj.ac/problem/2526

题解

首先易知一共有 \(n!\) 种形态的二叉树,所以我们实际上求的是所有二叉树不便度的总和。

计算每个点对之间的贡献似乎不太好办,我们考虑计算路径经过某条边的点对个数。

一个显然的事实是:假如切掉一条边 \(u \to v\),将这棵树分为大小分别为 \(s\) 和 \(n-s\) 的两部分,则经过这条边的点对数为 \(2s(n-s)\)(\((u,v)\) 和 \((v,u)\) 算两次)。

现在我们按编号从小到大插入每一个点(点的插入顺序显然不影响结果)。

每插入一个点,我们枚举以这个点的子节点为根的子树大小 \(s\)。根据上面的叙述,可以知道,当前点和当前点的子节点之间的这条边,会对答案产生 \(2s(n-s)\) 的贡献。

假如我们现在正在插入第 \(i\) 个点,我们来考虑这几个事实:

  1. 对于前 \(i\) 个点,一共有 \(i!\) 种形态的二叉树;
  2. 从剩下的 \(n-i\) 个点中选 \(s\) 个点挂到 \(i\) 下面,一共有 \(C_{n-i}^s\) 种选法,再乘以 \(s!\) 的形态数,共有 \(s!C_{n-i}^s\) 种方案;
  3. 对于剩下的 \(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;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据