题目

{% fold 点击显/隐题目 %}

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

Hint
最后结果需要高精度

n，n<1000。

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

1

3

{% endfold %}

题解

画图找规律,可以发现:
$F(1)=3$
$F(2)=11$
$F(3)=3*f(2)+2*f(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

代码

{% fold 点击显/隐代码 %}```cpp 骨牌问题 https://github.com/OhYee/sourcecode/tree/master/ACM 代码备份
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);
    }
}

}

{% endfold %}

AOJ 880.骨牌问题