[UVA][math][JAVA] 10643 - Facing Problem With Trees
Facing Problem With Trees
Input: standard input
Output: standard output
Time
Limit: 3 seconds
In this problem you are to find the number ( Let P ) of ordered trees where each of the tree consists of exactly m edges and each of the nodes has out-degree either exactly two or zero and the root has even out-degree. For example, if there are four edges, we get the following three trees.
Input
The first line in the input file is an integer representing
the number of test cases. Each of the test cases follows below. Each case
consists an integer representing various even values of m ( 2 ≤ m
≤ 500 ).
Output
For each test case, first print the serial number of the case and then print the value of P separated by an space from the serial number. You should use Big Integer operation to print P and P has maximum 200 digits.
Sample
Input
3
4
10
14
Sample Output
Case 1: 3
Case 2: 126
Case 3: 1716
Problem setter: Anupam Bhattacharjee, CSE, BUET
Thanks to Adrian Kuegel for his alternate solution.
"~~
NP ≠
P as NP means never possible and P means possible. Where is my Turing award of
2999?? ~~"
思路很簡單，把卡塔蘭數(Catalan number)抓來使用。
然後 dp[i][j] 表示節點個數 i 個, 根節點具有 j 個分支。
因此 j 一定為偶數，對於卡塔蘭數 F[i] 代表有 2*i+1 個節點(補滿 dummy node)。
那麼可以得到 dp[i][j-2] += dp[i-f1-f2]*F[ff1]*[ff2]
f1 是新增的第一分支的節點個數， F[ff1] 是這個樹的方法數(即卡塔蘭數)
同理 f2, ff2。
import java.util.*;
import java.math.BigInteger;
public class Main {
static BigInteger[] F = new BigInteger[255];
static BigInteger[] F2 = new BigInteger[505];
static BigInteger[][] dp = new BigInteger[505][505];
public static void main(String[] args) {
F[0] = BigInteger.ONE;
for (int i = 1; i < 255; i++) {
F[i] = F[i - 1].multiply(BigInteger.valueOf(4 * i - 2)).divide(
BigInteger.valueOf(i + 1));
}
for (int i = 0; i < 505; i++)
F2[i] = BigInteger.ZERO;
for (int i = 0; i < 255; i++) {
for (int j = 0; j < 255; j++) {
if (i * 2 + 1 + j * 2 + 1 >= 505)
break;
F2[i * 2 + 1 + j * 2 + 1] = F2[i * 2 + 1 + j * 2 + 1].add(F[i]
.multiply(F[j]));
}
}
for (int i = 0; i < 505; i++)
for (int j = 0; j < 505; j++)
dp[i][j] = BigInteger.ZERO;
dp[0][0] = BigInteger.valueOf(1);
dp[1][0] = BigInteger.valueOf(1);
dp[3][2] = BigInteger.valueOf(1);
for (int i = 5; i < 505; i += 2) {
dp[i][2] = F[(i - 1) / 2];
for (int j = 4; j < i; j += 2) {
for (int k = 2; k <= i; k += 2) {
dp[i][j] = dp[i][j].add(dp[i - k][j - 2].multiply(F2[k]));
}
}
}
Scanner cin = new Scanner(System.in);
int testcase = cin.nextInt(), cases = 0;
while (testcase-- != 0) {
int n = cin.nextInt();
BigInteger ret = BigInteger.ZERO;
for (int i = 2; i <= n; i++)
ret = ret.add(dp[n + 1][i]);
System.out.printf("Case %d: %s\n", ++cases, ret);
}
}
}