[HNOI2008 Tree]

[キーワード]:Prüfer符号化Cayleyの定理
[题目大意]:N结点の木の上の部分の点の度数を教えて、このような木が全部で何本あることを求めます.
//==================================================================================
[分析]:この問題を見たばかりの頃は少しも考えられなかったが、しばらく考えていたが、まだ考えられなかった......この問題はPrüfer符号化Cayleyの定理と関係があり、Cayleyの定理:nノードの無根樹にはnn-2の形態がある.この定理はPrüfer符号化によって証明することができ,ここを参照する.Prüfer符号化の普及によりn各右度制限ノードの無根ツリーの個数が得られるが,n各有度制限の無根ツリーの個数はどのように計算されるのか.まず有度制限の先を計算します.
tot!/(d1-1)!/(d2-1)!……/(di-1)!(totは全度の和)実n-2位置の中からtot個を選択するのでC(n-2,tot)を乗じることもあり,残りの度制限のないノードはn-2-tot位置に置く必要があり,合計
(n-tot)(n-2-tot)種のシナリオなので、合計シナリオ数は:(n-tot)(n-2-tot)*C(n-2,tot)*tot!/(d1-1)!/(d2-1)!……/(di-1)!,計算を少し簡略化し,除算は分解素因数乗算で高精度にする.
[コード]:

#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("
");
}

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