bzoj1211: [HNOI2004]树的计数 prufer序列裸题

时间:2022-12-26 16:24:34

一个有n个结点的树,设它的结点分别为v1, v2, …, vn,已知第i个结点vi的度数为di,问满足这样的条件的不同的树有多少棵。给定n,d1, d2, …, dn,编程需要输出满足d(vi)=di的树的个数。

答案是(n-2)!/(a[1]-1)!/.../(a[n]-1)!,要特判一下不满足的情况和n==1的情况

bzoj1211: [HNOI2004]树的计数 prufer序列裸题bzoj1211: [HNOI2004]树的计数 prufer序列裸题
/**************************************************************
    Problem: 1211
    User: walfy
    Language: Java
    Result: Accepted
    Time:560 ms
    Memory:17892 kb
****************************************************************/
 
import java.math.BigInteger;
import java.util.*;
 
public class Main {
 
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int n = cin.nextInt();
        int[] a = new int [200];
        boolean ok = true;
        int sum=0;
        for(int i=0;i<n;i++)
        {
            a[i]=cin.nextInt();
            if(a[i] == 0)ok=false;
            sum += a[i];
        }
        if(n==1)
        {
            if(a[0]==0)System.out.println(1);
            else System.out.println(0);
            return ;
        }
        if(ok == false||sum != 2*n-2)
        {
            System.out.println(0);
            return ;
        }
        BigInteger [] b = new BigInteger [200];
        b[0] = BigInteger.ONE;
        for(int i=1;i<200;i++)
        {
            b[i]=b[i-1].multiply(BigInteger.valueOf(i));
        }
        BigInteger ans = b[n-2];
        for(int i=0;i<n;i++)
        {
            ans=ans.divide(b[a[i]-1]);
        }
        System.out.println(ans);
    }
}
View Code