poj 2506Tiling 大数

Tiling Time Limit: 1000MS Memory Limit: 65536KTotal Submissions: 9971 Accepted: 4681

Description

In how many ways can you tile a 2xn rectangle by 2x1 or 2x2 tiles?  Here is a sample tiling of a 2x17 rectangle. 

Input

Input is a sequence of lines, each line containing an integer number 0 <= n <= 250.

Output

For each line of input, output one integer number in a separate line giving the number of possible tilings of a 2xn rectangle. 

Sample Input

2 8 12 100 200

Sample Output

3 171 2731 845100400152152934331135470251 1071292029505993517027974728227441735014801995855195223534251

Source

The UofA Local 2000.10.14 import java.io.*; import java.math.BigInteger; import java.util.*; public class Main { public static void main(String args[]) { Scanner cin = new Scanner(System.in); int n; BigInteger a[] = new BigInteger[255]; while(cin.hasNext()) { a[0] = BigInteger.valueOf(1); a[1] = BigInteger.valueOf(1); a[2] = BigInteger.valueOf(3); n = cin.nextInt(); for(int i = 3; i <= n; ++i) a[i] = a[i - 1].add(a[i - 2]).add(a[i - 2]); System.out.println(a[n]); } } }