UVa 10694 - Combinatorial Summation

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

對於組合公式,輸出其結果。

Sample Input

1
2
3
2
3
4

Sample Output

1
2
7
14

Solution

暴力法將前幾項找出來,發現其相鄰兩項之差恰好有規律。

1
2
0 1 3 7 14 26 46 79 133 
0 2 4 7 12 20 33 54

其規律是前兩項總和再加一。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import java.util.Scanner;
import java.math.BigInteger;

public class Main {
public static void main(String[] args) {
BigInteger[] f1 = new BigInteger[1024];
BigInteger[] f2 = new BigInteger[1024];
f1[1] = BigInteger.valueOf(2);
f1[2] = BigInteger.valueOf(4);
f2[0] = BigInteger.valueOf(0);
f2[1] = BigInteger.valueOf(1);
for (int i = 3; i < f1.length; i++)
f1[i] = f1[i - 2].add(f1[i - 1]).add(BigInteger.ONE);
for (int i = 2; i < f2.length; i++)
f2[i] = f2[i - 1].add(f1[i - 1]);
Scanner cin = new Scanner(System.in);
int testcase = cin.nextInt();
while (testcase-- != 0) {
int n = cin.nextInt();
if (n < 0)
n = 0;
System.out.println(f2[n]);
}
}
}
/*
* 0 1 3 7 14 26 46 79 133
0 2 4 7 12 20 33 54
*/