正題

題目大意:https://www.luogu.org/problem/P2290

---

題目大意

一棵樹無根樹第$i$個點(diǎn)的度數(shù)為$d_i$，求樹的數(shù)量。

---

解題思路

更具$prufer$序列的推論我們可以知道答案就是$$\frac{(n?2)!}{{\prod }_{i=1}^n(d_i?1)!}$$

然后這就是有重復(fù)重排的式子，所以就是要求$n?2$個數(shù)，$i$有$d_i?1$個，求排列數(shù)。

組合數(shù)計(jì)算即可。

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=151; ll n,d[N],c[N][N],ans=1,sum; int main() {scanf("%lld",&n);for(ll i=1;i<=n;i++)scanf("%lld",&d[i]),sum+=d[i]-1;if(sum!=n-2){printf("0");return 0;}c[0][0]=1;for(ll i=0;i<=n;i++)for(ll j=1;j<=i;j++)c[i][j]=c[i-1][j-1]+c[i-1][j];sum=0;for(ll i=1;i<=n;i++)ans*=c[n-sum-1][d[i]],sum+=d[i]-1;printf("%lld",ans); }

總結(jié)

以上是生活随笔為你收集整理的P2290-[HNOI2004]树的计数【组合数,Prufer序列】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。