PKU 2506-Tiling

問題概要

2xnのマス目を1x2のタイルと2x2のタイルで敷き詰める方法は何通りあるか求めよ．

解法

漸化式はA_n=A_n-1+2A_n-2になる．
多倍長整数を使うだけ

実装(Java)

import java.util.*;
import java.math.*;
import java.io.*;
import java.util.regex.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;
import static java.lang.System.*;

public class Main {
	Scanner input;

	void run(){
		input=new Scanner(System.in);
		while(input.hasNext()){
			int t=input.nextInt();
			BigInteger now=BigInteger.ONE;
			BigInteger back1=BigInteger.ONE;
			BigInteger back2=BigInteger.ZERO;
			for(int i=0;i<t;i++){
				now=back1.add(back2.add(back2));
				back2=back1;
				back1=now;
			}
			printf("%s\n",now.toString());
		}
	}

	void printf(String format,Object... args){
		System.out.printf(format, args);
	}

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

}