PKU 2680 Computer Transformation
http://poj.org/problem?id=2680
与えられた数字列を指定された方法でn回変換した後に、00という数字列がいくつ存在するかというような問題。
00というのは01という数字の並びから1つ生成され、01という数字の並びは、1と00の二つの数字の並びから一つずつ生成される。それを漸化式にして書いた。
多倍長を使うのが面倒だったのでjavaに逃げました。
あんまりBigIntegerとかにはまだ慣れません
import java.math.BigInteger; import java.util.*; public class Main { public static BigInteger[][] dp=new BigInteger[1001][3]; public static void main(String args[]) throws Exception { Scanner cin=new Scanner(System.in); dp[1][0]=new BigInteger("1"); dp[1][1]=new BigInteger("1"); dp[1][2]=new BigInteger("0"); for(int i=2;i<=1000;i++){ dp[i][0]=dp[i-1][0].add(dp[i-1][0]); dp[i][1]=dp[i-1][0].add(dp[i-1][2]); dp[i][2]=dp[i-1][1]; } while(cin.hasNextInt()){ int b=cin.nextInt(); if(b==0)break; System.out.println(dp[b][2].toString()); } } }