PKU 2506 Tiling

• 動的計画法
• 以下の三つのパターンを考えれば良い
  • 一つ前から縦のタイルを置くパターン
  • 二つ前から横のタイル二つを置くパターン
  • 二つ前から正方形のタイルを置くパターン
• 組み合わせの数が膨大になるため多倍長整数が必要となる
• nが64ビットまでかつmod何とかで答えよという場合は行列のn乗が必要となる

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
	private void run() {
		final BigInteger[] dp = new BigInteger[256];
		dp[0] = BigInteger.ONE;
		dp[1] = BigInteger.ONE;
		for (int i = 2; i <= 250; ++i) {
			dp[i] = dp[i - 2].multiply(BigInteger.valueOf(2)).add(dp[i - 1]);
		}

		final Scanner scanner = new Scanner(System.in);
		while (scanner.hasNextInt()) {
			final int n = scanner.nextInt();
			System.out.println(dp[n].toString());
		}
	}

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