URAL 1387 Vasya's Dad

題目大意：

定義beautiful directed graph 為有根樹

實際上就是求有n個結點的有根樹的數量

這個題聽學長說他們使用排列組合+背包做的，，表示不懂，，

不過有根樹的個數是有公式的，，于是這個就變成了一個結論題了麼，，

關于有根樹的計數

設有i個結點的有根樹的總數為 a[i]

那麼有設S[n][j]為

那麼有

其中a[1] = 1,a[2] = 1,a[3] = 2,a[4] = 4,a[5] = 9, a[6] = 20,a[9] = 286,a[11] = 1842

這裡在寫代碼的時候我沒有建立數組S，直接跑的循環，，

求a[50] 會超出 long long 的範圍，要用高精度

另外，高精度用C++寫比較麻煩吧，，，是以第一次做OJ的題用了Java，，，

Result  :  Accepted     Memory  :  1936 KB     Time  :  156 ms

/*
 * Author: Gatevin
 * Created Time:  2014/7/23 15:31:03
 * File Name: test.java
 */
import java.math.BigInteger;
import java.io.PrintWriter;
import java.util.Scanner;
public class haha{
    public static void main(String args[]){
    BigInteger a[] = new BigInteger[51];
    a[0] = BigInteger.valueOf(0);
    a[1] = BigInteger.valueOf(1);
    a[2] = BigInteger.valueOf(1);
    a[3] = BigInteger.valueOf(2);
    BigInteger tmp1;
    BigInteger tmp2;
    Scanner in=new Scanner(System.in);
    int N=in.nextInt();
    for(int n = 3; n <= N; n++)
    {
        tmp1 = BigInteger.valueOf(0);
        for(int j = 1; j <= n - 1; j++)
        {
            tmp2 = BigInteger.valueOf(0);
            for(int k = 1; k <= (n - 1)/j; k++)
            {
                tmp2 = tmp2.add(a[n - k*j]);
            }
            tmp2 = tmp2.multiply(BigInteger.valueOf(j));
            tmp2 = tmp2.multiply(a[j]);
            tmp1 = tmp1.add(tmp2);
        }
        a[n] = tmp1.divide(BigInteger.valueOf(n - 1));
    }
    System.out.println(a[N]);
    }
}