# Poj Solution 1737

```http://poj.org/problem?id=1737

import java.util.*;
import java.math.*;

public class Main
{
BigInteger[] ans = new BigInteger;
public Main()
{
DP();
solve();
}
//求组合数
BigInteger combinationNum(int n, int m)
{
BigInteger ret = new BigInteger("1");
int i;
for (i = 0; i < m; ++i)
{
ret = ret.multiply(new BigInteger(n - i + ""));
ret = ret.divide(new BigInteger(i + 1 + ""));
}
return ret;
}

void DP()
{
ans = new BigInteger("1");
ans = new BigInteger("1");
int i, j;
BigInteger tmp = new BigInteger("0");
BigInteger com = new BigInteger("0");
for (i = 3; i <= 50; ++i)
{
ans[i] = new BigInteger("0");
for (j = 1; j < i; ++j)
{
com = combinationNum(i - 2, j - 1);
tmp = ans[j].multiply(ans[i - j]);
tmp = tmp.multiply(com);
tmp = tmp.multiply(new BigInteger(((long)1 << j) - 1 + ""));
}
}
//for (i = 1; i <= 50; ++i)
//   System.out.println(i + ": " + ans[i]);
}
void solve()
{
int n;
Scanner cin = new Scanner(System.in);
while (true)
{
n = cin.nextInt();
if (n == 0)
return;
System.out.println(ans[n]);
}
}

public static void main(String args[])
{
new Main();
}
}

```
This entry was posted in poj. Bookmark the permalink.