AOJ 880.骨牌问题

204


题目



点击显/隐题目

Description
已知3×2n个棋盘格子,试求用火柴棒覆盖所有格子的方法(一根火柴棒可覆盖2个格子)。
如n=1时,有如下3种覆盖方法:



Hint
最后结果需要高精度


n,n<1000。


用火柴棒覆盖所有3×2n格子的方案数。


1


3




题解


画图找规律,可以发现:
$F(1)=3$
$F(2)=11$
$F(3)=3f(2)+2f(1)+2$

$f(n)=3f(n-1)+2f(n-2)+2f(n-3)+2f(n-4)+2f(n-5)+......+2f(1)+2$
$f(n)=3f(n-1)-f(n-2)+(3f(n-2)+2f(n-3)+2f(n-4)+2f(n-5)+......+2f(1)+2$
$f(n)=3f(n-1)-f(n-2)+f(n-1)$
$f(n)=4*f(n-1)-f(n-2)$

使用高精度算法即可

高精度模板有问题,使用java


代码


点击显/隐代码
import java.util.*;
import java.io.*;
import java.math.*;

public class a {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);

Integer n;

BigDecimal x, y, z;
while (in.hasNext()) {
n = in.nextInt();

if (n == 0) {
System.out.println(0);
continue;
}
BigInteger dp_1 = BigInteger.valueOf(3);
BigInteger dp_2 = BigInteger.valueOf(1);
BigInteger dp = BigInteger.valueOf(3);

for (int i = 1; i < n; i++) {
dp = dp_1.multiply(BigInteger.valueOf(4)).subtract(dp_2);

dp_2 = dp_1;
dp_1 = dp;
}
System.out.println(dp);
}
}
}
发布评论
  • 点击查看/关闭被识别为广告的评论