Problem Specification Value
Time Limit 1 Sec
Memory Limit 162 MB
Submit 3972
Solved 1579

Description

自从明明学了树的结构, 就对奇怪的树产生了兴趣...... 给出标号为 1 到 N 的点, 以及某些点最终的度数, 允许在
任意两点间连线, 可产生多少棵度数满足要求的树?

Input

第一行为 N (0 < N <=1000), 接下来 N 行, 第 i+1 行给出第 i 个节点的度数 Di, 如果对度数不要求, 则输入-1

Output

一个整数, 表示不同的满足要求的树的个数, 无解输出 0

Sample Input

3
1
-1
-1

Sample Output

2

HINT

两棵树分别为 1-2-3; 1-3-2

Source

这题需要了解一种数列:Prufer Sequence

我们知道, 一棵树可以用括号序列来表示, 但是, 一棵顶点标号 (1~ n) 的树, 还可以用一个叫做 Prufer Sequence 的数列表示

一个含有 n 个节点的 Prufer Sequence 有 n-2 个数, Prufer Sequence 中的每个数是 1~ n 中的一个数

一个定理: 一个 Prufer Sequence 和一棵树一一对应

化简之后为:\(res = \frac{(n - 2)!}{(n - 2 - sum)! \times \pi^{cnt}_{i = 1} (d[i] - 1)} \times (n - cnt)^{n - 2 - sum}\)

在有解的情况下, 计算该结果输出就行了

无解的情况非常好确定, 这里就再讨论了

话说为什么调了半天还是在第一个点 WA~

// SAMPLE CODE FROM HZWER
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#define mod 1000000
#define ll long long
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x*=10;x+=ch-'0';ch=getchar();}
    return x*f;
}
int n,m,tot,cnt;
int d[1005],num[1005],pri[1005];
int ans[1005],l=1;
inline bool jud(int x)
{
     for(int i=2;i<=sqrt(x);i++)
         if(x%i==0)return 0;
     return 1;
}
void getpri()
{
     for(int i=2;i<=1000;i++)
         if(jud(i))pri[++cnt]=i;
}
void solve(int a,int f)
{
     for(int k=1;k<=a;k++)
     {
         int x=k;
         for(int i=1;i<=cnt;i++)
         {
             if(x<=1)break;
             while(x%pri[i]==0)
             {num[i]+=f;x/=pri[i];}
         }
     }
}
void mul(int x)
{
    for(int i=1;i<=l;i++)
        ans[i] = ans[i] * x;
    for(int i=1;i<=l;i++)
    {
        ans[i+1]+=ans[i]/mod;
        ans[i]%=mod;
    }
    while(ans[l+1]>0)
    {l++;ans[l+1]+=ans[l]/mod;ans[l]%=mod;}
}
void print()
{
    for(int i=l;i>0;i--)
        if(i==l)printf("%d",ans[i]);
        else printf("%06d",ans[i]);
}
int main()
{
     getpri();ans[1]=1;
     n=read();
     if(n==1)
     {
         int x=read();
         if(!x)printf("1");
         else printf("0");
         return 0;
     }
     for(int i=1;i<=n;i++)
     {
         d[i]=read();
         if(!d[i]){printf("0");return 0;}
         if(d[i]==-1)m++;
         else {d[i]--;tot+=d[i];}
     }
     if(tot>n-2){printf("0");return 0;}
     solve(n-2,1);
     solve(n-2-tot,-1);
     for(int i=1;i<=n;i++)
         if(d[i])solve(d[i],-1);
     for(int i=1;i<=cnt;i++)
         while(num[i]--)
             mul(pri[i]);
     for(int i=1;i<=n-2-tot;i++)
         mul(m);
     print();
     return 0;
}
// FALSE CODE, RESERVED FOR DEBUGGING
// FALSE CODE, RESERVED FOR DEBUGGING
// FALSE CODE, RESERVED FOR DEBUGGING
// FALSE CODE, RESERVED FOR DEBUGGING
// FALSE CODE, RESERVED FOR DEBUGGING
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <cstdio>
#include <map>

using namespace std;
const int maxn = 1100, modr = 100000000;

// High precision modules

long long   hpdat[maxn];
int         hplen = 0;

void hpinit(void) { hplen = 1; hpdat[1] = 1; return ; }
void hpmult(int v)
{
    for (int i = 1; i <= hplen; i++) hpdat[i] *= v;
    for (int i = 1; i <= hplen; i++) hpdat[i + 1] += hpdat[i] / modr, hpdat[i] %= modr;
    if (hpdat[hplen + 1] > 0) hplen++;
    return ;
}
void hpprint()
{
    cout << hpdat[hplen];
    for (int i = hplen - 1; i >= 1; i--)
        cout << setfill('0') << setw(8) << hpdat[i];
    cout << endl << flush;
    return ;
}

// Main program procedure

int             n, d[maxn], sum, cnt;
int             primes[maxn], primecnt;
map<int, int>   facts;
long long       result = 0;

void genprimes(void)
{
    primecnt = 0;
    primes[++primecnt] = 2;
    for (int i = 3; i <= maxn; i++) {
        bool isprime = true;
        for (int j = 1; j <= primecnt && primes[j] * primes[j] < i; j++)
            if (i % primes[j] == 0) {
                isprime = false;
                break;
            }
        if (!isprime) continue;
        primes[++primecnt] = i;
    }
    facts.clear();
    for (int i = 1; i <= primecnt; i++)
        facts[primes[i]] = 0;
    return ;
}

void factor(int x, int dup)
{
    for (int i = 1; i <= maxn && x > 1; i++) {
        int p = primes[i], q = 0;
        while (x % p == 0) x /= p, q++;
        if (!q) continue;
        facts[p] += q * dup;
    }
    return ;
}

int main(int argc, char** argv)
{
    scanf("%d", &n);
    if (n == 1) {
        scanf("%d", &d[1]);
        if (d[1] == 0) printf("1\n");
        else printf("0\n");
        return 0;
    }
    for (int i = 1; i <= n; i++) {
        scanf("%d", &d[i]);
        if (d[i] == 0) {
            goto no_result;
        } else if (d[i] > 0) {
            sum += d[i] - 1;
            cnt++;
        }
    }
    if (sum > n - 2)
        goto no_result;
    genprimes();
    // Initialize formulae from solution
    for (int i = n - 2 - sum + 1; i <= n - 2; i++)
        factor(i, 1);
    for (int i = 1; i <= n; i++)
        if (d[i] != -1)
            factor(d[i] - 1, -1);
    factor(n - cnt, n - 2 - sum);
    // Apply final results to high-precision number
    hpinit();
    for (int i = 1; i <= primecnt; i++) {
        int p = primes[i], q = facts[p];
        for (int j = 1; j <= q; j++)
            hpmult(p);
    }
    hpprint();
    return 0;
no_result:
    printf("0\n");
    return 0;
}
from pydatagen import *
n = randrange(1, 1000)
sum = 0
print('%d\n' % n)
for i in range(0, n):
    a = randrange(1, 4)
    if a + sum < (n - 2) / 2:
        sum += a
        printf('%d\n' % a)
    else:
        printf('-1\n')
fclose()