UVa 10334 Ray Through Glasses(フィボナッチ&高精度)

10334 - Ray Through Glasses
Time limit: 3.000 seconds
http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1275
Suppose we put two panes of glass back-to-back. How many ways  are there for light rays to pass through or be reflected after changing direction n times ? Following figure shows the situations when the value of nis 0, 1 and 2.                                    
Input 
It is a set of lines with an integer n where 0 <= n <= 1000 in each of them.
Output 
For every one of these integers a line containing  as described above.
Sample Input 

0
1
2

Sample Output 

1
2
3

anについて、もし私たちが真ん中のガラスで反射したら、後ろは上のガラスで一度反射しなければなりません.後ろの状況数はa(n-2)です.下の層で反射すると,後のケース数はa(n−1)である.
だからan=a(n-1)+a(n-1)
しかしnは最大1000であり,フィボナッチ数列が指数関数的に増加することを考慮して高精度で処理する.
完全なコード:

/*0.022s*/

#include <cstdio>

int F[1005][60];

int main(void)
{
	F[0][0] = 1, F[1][0] = 2;
	for (int i = 2; i <= 1000; ++ i)
	{
		for (int j = 0 ; j < 55 ; ++ j)
			F[i][j] = F[i - 1][j] + F[i - 2][j];
		for (int j = 0; j < 55; ++ j)
		{
			F[i][j + 1] += F[i][j] / 10000;///    
			F[i][j] %= 10000;///   4 
		}
	}
	int n;
	while (~scanf("%d", &n))
	{
		int end = 55;
		while (end > 0 && !F[n][end]) --end;
		printf("%d", F[n][end--]);
		while (end >= 0) printf("%04d", F[n][end--]);///    
		printf("
");
	}
	return 0;
}

/*0.582s*/

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

public class Main {
	static final int maxn = 1001;
	static Scanner cin = new Scanner(new BufferedInputStream(System.in));

	public static void main(String[] args) {
		BigInteger[] f = new BigInteger[maxn];
		f[0] = BigInteger.ONE;
		f[1] = BigInteger.valueOf(2);
		for (int i = 2; i < maxn; ++i)
			f[i] = f[i - 1].add(f[i - 2]);
		while (cin.hasNextInt())
			System.out.println(f[cin.nextInt()]);
	}
}