BZOJ1005:[HNOI2008]明明的烦恼(组合数学,Prufer)

àì夳堔傛蜴生んèń 2021-12-22 05:43 147阅读 0赞

## Description ##

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

## Input ##

第一行为N(0 < N < = 1000),

接下来N行,第i+1行给出第i个节点的度数Di,如果对度数不要求,则输入-1

## Output ##

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

## Sample Input ##

3  
1  
\-1  
\-1

## Sample Output ##

## HINT ##

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

## Solution ##

[屠龙宝刀点击再送][Link 1]

要写高精度和质因数分解。

## Code ##

1 #include<iostream>
     2 #include<cstring>
     3 #include<cstdio>
     4 #include<cmath>
     5 #include<algorithm>
     6 #define N (3009)
     7 #define MAX_L 10009
     8 using namespace std;
     9 
    10 int n,m,rem,d,ans[N],cnt[N];
    11 
    12 void Divide(int x,int opt)
    13 {
    14     for (int i=2; i<=sqrt(x); ++i)
    15         while (x%i==0) x/=i,cnt[i]+=opt;
    16     if (x>1) cnt[x]+=opt;
    17 }
    18 
    19 void Mul(int *a,int b)
    20 {
    21     int g=0;
    22     for (int i=1; i<=a[0]; ++i)
    23         a[i]=a[i]*b+g,g=a[i]/10,a[i]%=10;
    24     while (g) a[0]++,a[a[0]]=g%10,g/=10;
    25 }
    26 
    27 int main()
    28 {
    29     ans[0]=ans[1]=1;
    30     scanf("%d",&n); rem=n-2;
    31     for (int i=1; i<=n-2; ++i) Divide(i,1);
    32     for (int i=1; i<=n; ++i)
    33     {
    34         scanf("%d",&d);
    35         if (!d && n>1) {puts("0"); return 0;}
    36         if (d==-1) {++m; continue;}
    37         if ((rem=rem-(d-1))<0) {puts("0"); return 0;}
    38         for (int j=1; j<=d-1; ++j) Divide(j,-1);
    39     }
    40     if (n==1)
    41     {
    42         if (d==-1 || d==0) puts("1");
    43         else puts("0");
    44         return 0;
    45     }
    46     for (int i=1; i<=rem; ++i) Divide(i,-1);
    47     for (int i=1; i<=rem; ++i) Divide(m,1);
    48     for (int i=1; i<=n; ++i)
    49         for (int j=1; j<=cnt[i]; ++j)
    50             Mul(ans,i);
    51     for (int i=ans[0]; i>=1; --i)
    52         printf("%d",ans[i]);
    53 }

转载于:https://www.cnblogs.com/refun/p/10227498.html

[Link 1]: https://www.cnblogs.com/dirge/p/5503289.html