hdu 1130 How Many Trees?
1088 ワード
この問題は簡単なcatalan数の応用であり,二叉木の表現方法はカトラン数に乗る典型的な括弧の合法的な種類数の問題を変換することができる.
私の考えは、木の深さで順番を探して初めて1つの点を通るときに左かっこを描くと、このノードの左ノードが便利に完成してからこの点に戻ります.これは右かっこを描くことです.そうすれば、木ごとに1つの合法的なかっこのシーケンスに唯一対応することができ、1つの合法的な括弧のシーケンスページごとに1つの木に唯一対応することができます.そうすると、この問題は最も簡単なcatalan数に変換されます.
この問題は高精度に使われるので、javaを直接使います.
私の考えは、木の深さで順番を探して初めて1つの点を通るときに左かっこを描くと、このノードの左ノードが便利に完成してからこの点に戻ります.これは右かっこを描くことです.そうすれば、木ごとに1つの合法的なかっこのシーケンスに唯一対応することができ、1つの合法的な括弧のシーケンスページごとに1つの木に唯一対応することができます.そうすると、この問題は最も簡単なcatalan数に変換されます.
この問題は高精度に使われるので、javaを直接使います.
import java.util.*;
import java.math.*;
public class Main{
public static void main(String args []){
int a;
Scanner scan= new Scanner(System.in);
while(scan.hasNext()){
a = scan.nextInt();
solve(a);
}
}
static void solve(int a){
BigInteger ans;
ans = new BigInteger("1");
BigInteger b;
for(int i =1;i<=a;i++){
int c = 4*i -2 ;
int d = i +1;
b= new BigInteger(c+"");
ans = ans.multiply(b);
b = new BigInteger(d+"");
ans = ans.divide(b);
// System.out.println(ans + " "+ a);
}
System.out.println(ans);
}
}