About Problem

• The web : http://www.lydsy.com/JudgeOnline/problem.php?id=1005
• The tab : Prufer編碼，組合數(shù)學

Solve

要完成這道題需要先了解Prufer Sequence。
可以借鑒大牛博客：傳送門
大致了解后，題目就變成了：

給你一串數(shù)，給出你每個數(shù)在Prufer Sequence中出現(xiàn)的次數(shù)，-1代表無限制，要你求出所有可能的Prufer Sequence。

于是就變成一道組合數(shù)學。

• tot代表所有數(shù)的 (d[i] - 1)， cnt代表所有出現(xiàn)次數(shù)有限制的數(shù)的個數(shù)

這個的意思就是把第i個數(shù)拆成 d[i] - 1 個相同的數(shù)，每個數(shù)放進tot個Prufer Sequence里面。

• tot個Prufer Sequence一共有C^tot_(n-2)（看不懂下面有配圖）種情況。

C^tot_(n-2)

• 然后第一個Sequence里面有tot個數(shù)可以選擇，第二個Sequence里面有 tot-1 個數(shù)可以選擇 …… 以此類推，每個數(shù)由于在每個位置上會選擇d[i] - 1次，所以會有prod_1^cnt ((d[i-1])!)次重復。

  
  
  prod_1^cnt ((d[i-1])!)

• 所以一共可能的Prufer Sequence有：

  
  

然后用高精度，求出答案，就很簡單了。

• 代碼：

#include <cstdio>
#ifdef _WIN32
#define lld I64d
#endif

typedef long long ll;

const int Maxn = 1010;
int prime[200], num[Maxn][200], d[Maxn], ans[200];
int n, tot = 0, cnt = 0, sum = 0, a[Maxn] = {1, 1};
bool vis[Maxn];

int get_prime()
{
    for(int i = 2; i <= 1000; ++i)
    {
        if(vis[i]) continue;
        prime[++prime[0]] = i;
        for(int j = 2; i * j <= 1000; ++j) vis[i * j] = true;
    }
    for(int i = 2; i <= 1000; ++i)
        for(int j = 1; j <= prime[0]; ++j)
        {
            int tmp = i;
            while(tmp % prime[j] == 0)
            {
                ++num[i][j];
                tmp /= prime[j];
            }
        }
    return prime[0];
}

void add(int x, int k)
{
    for(int i = 1; i <= prime[0]; ++i)
        ans[i] += x * num[k][i];
    return;
}

void cheng(int x)
{
    for(int i = 1; i <= a[0]; ++i) a[i] *= x;
    for(int i = 1; i <= a[0]; ++i)
        if(a[i] >= 10000) a[i + 1] += a[i] / 10000, a[i] %= 10000;
    if(a[a[0] + 1]) ++a[0];
    return;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("1005.in", "r", stdin);
#endif

    scanf("%d", &n);
    get_prime();
    for(int i = 1; i <= n; ++i)
    {
        scanf("%d", d + i);
        if(d[i] == 0)
        {
            printf("0\n");
            return 0;
        }
        if(d[i] == -1) ++cnt;
        else ++tot, sum += d[i] - 1;
    }
//  printf("%d\n", sum);
    if(sum > n - 2)
    {
        printf("0\n");
        return 0;
    }
    for(int i = n - 1 - sum; i <= n - 2; ++i) add(1, i);
    add(n - 2 - sum, cnt);
    for(int i = 1; i <= n; ++i)
        if(d[i] != -1)
        for(int j = 1; j <= d[i] - 1; ++j) add(-1, j);
    for(int i = 1; i <= prime[0]; ++i)
        for(int j = 1; j <= ans[i]; ++j) cheng(prime[i]);
    printf("%d",a[a[0]]);
    for(int i = a[0] - 1; i; --i) printf("%04d",a[i]);
    printf("\n");
    return 0;
}