[關(guān)鍵字]：Prüfer編碼?Cayley定理

[題目大意]：告訴你N結(jié)點(diǎn)的樹(shù)上部分點(diǎn)的度數(shù),求這樣的樹(shù)一共有多少棵.

//==================================================================================

[分析]：剛剛看到這題時(shí)一點(diǎn)思路也沒(méi)有，又想了一會(huì)兒，還是沒(méi)思路……這題其實(shí)和Prüfer編碼Cayley定理有關(guān)系，Cayley定理：一個(gè)n個(gè)節(jié)點(diǎn)的無(wú)根樹(shù)有n^n-2種形態(tài)。這個(gè)定理可以通過(guò)Prüfer編碼來(lái)證明，見(jiàn)這里。通過(guò)Prüfer編碼的推廣可以得到n各右度限制的節(jié)點(diǎn)的無(wú)根樹(shù)的個(gè)數(shù)，而n各有些有度限制的無(wú)根樹(shù)個(gè)數(shù)怎么算呢？首先把有度限制的先算出來(lái)：

tot!/(d1-1)!/(d2-1)!……/(di-1)!(tot是所有度之和)，因?yàn)閷?shí)在n-2個(gè)位置中選出tot個(gè)所以還有再乘C(n-2,tot)，而剩下的沒(méi)有度限制的節(jié)點(diǎn)需要放在n-2-tot個(gè)位置，一共有

(n-tot)^(n-2-tot)種方案，所以總共的方案數(shù)為：(n-tot)^(n-2-tot)*C(n-2,tot)*tot!/(d1-1)!/(d2-1)!……/(di-1)!，稍微化簡(jiǎn)一下計(jì)算，除法要用分解質(zhì)因數(shù)乘法要用高精度。

[代碼]：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int MAXN=10000;

int n,tot,now,c,sum;
int a[MAXN],s[MAXN],p[MAXN];
int ans[MAXN];
bool v[MAXN];

void Add(int x,int c)
{
for (int i=1;i<=sum;++i)
while (x%s[i]==0)
{
p[i]+=c;
x/=s[i];
}
}

void Cheng(int t)
{
int k=0;
for (int i=1;i<=c;++i)
{
ans[i]=ans[i]*t+k;
k=ans[i]/10;
ans[i]=ans[i]%10;
}
while (k)
{
ans[++c]=k%10;
k=k/10;
}
}

void Init()
{
scanf("%d",&n);
for (int i=1;i<=n;++i)
{
scanf("%d",&a[i]);
if (a[i]!=-1) tot+=a[i]-1; else ++now;
}
memset(v,0,sizeof(v));
for (int i=2;i<=n;++i)
{
if (!v[i]) s[++sum]=i;
for (int j=1;(j<=sum && i*s[j]<=n);++j)
{
v[i*s[j]]=1;
if (i%s[j]==0) break;
}
}
}

void Solve()
{
for (int i=n-1-tot;i<=n-2;++i) Add(i,1);
for (int i=1;i<=n;++i)
if (a[i]!=-1)
for (int j=2;j<a[i];++j) Add(j,-1);
for (int i=1;i<=n-2-tot;++i) Add(now,1);
c=1;
ans[1]=1;
for (int i=1;i<=sum;++i)
for (int j=1;j<=p[i];++j)
Cheng(s[i]);
for (int i=c;i>=1;--i)
printf("%d",ans[i]);
printf("\n");
}

int main()
{
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
Init();
Solve();
return 0;
}

轉(zhuǎn)載于:https://www.cnblogs.com/procedure2012/archive/2012/04/06/2435496.html

總結(jié)

以上是生活随笔為你收集整理的[HNOI2008 Tree]的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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