正題

題目鏈接:https://www.luogu.com.cn/problem/P4492

---

題目大意

開始有一個節點，第$i$次在一個兒子不超過$2$的節點下面長出一個新兒子編號為$i$。求所有方案下樹的路徑長度和。

---

解題思路

考慮計算每條邊的貢獻，設$g_i$表示大小為$i$的樹的形態個數，$f_i$表示所有大小為$i$的樹的路徑長度和。然后題目給出的要求就是子節點編號比父節點大。

那么$g$有轉移$$g_{i+1}=\sum _{j=0}^i{g}_j{g}_{i?j}{C}_i^j$$
$f$的轉移復雜一點，枚舉子樹大小$j$和$i?j$，那么子樹$j$自己的貢獻就是$g_j?j?(n?j)$，然后要乘上$g_{i?j}$表示每種左子樹形態對應的樹的形態個數。右邊$i?j$同理，就有轉移方程$$f_{i+1}=\sum _{j=0}^i(g_i{g}_j(j?(n?j)+(i?j)?(n?i+j))+f_j?g_{i?j}+f_{i?j}?g_j)?C_i^j$$

時間復雜度$O(n^2)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=2100; ll n,p,f[N],g[N],c[N][N]; int main() {scanf("%lld%lld",&n,&p);g[0]=c[0][0]=1;for(ll i=1;i<=n;i++)for(ll j=0;j<=i;j++)c[i][j]=((j?c[i-1][j-1]:0)+c[i-1][j])%p;for(ll i=0;i<n;i++){for(ll j=0;j<=i;j++){(g[i+1]+=g[j]*g[i-j]%p*c[i][j])%=p;(f[i+1]+=(((i-j)*(n-i+j)%p+j*(n-j)%p)*g[j]%p*g[i-j]%p+f[j]*g[i-j]%p+f[i-j]*g[j]%p)%p*c[i][j]%p)%=p;}}printf("%lld\n",f[n]);return 0; }

總結

以上是生活随笔為你收集整理的P4492-[HAOI2018]苹果树【dp】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。