蓝桥杯每日一刷-创新互联

小明最近迷上了积木画, 有这么两种类型的积木, 分别为 II 型（大小为 2 个单位面积) 和 LL 型 (大小为 3 个单位面积):

同时, 小明有一块面积大小为 2 \times N2×N 的画布, 画布由 2 \times N2×N 个 1 \times 11×1 区域构 成。小明需要用以上两种积木将画布拼满, 他想知道总共有多少种不同的方式? 积木可以任意旋转, 且画布的方向固定。

输入一个整数 NN，表示画布大小。

输出一个整数表示答案。由于答案可能很大，所以输出其对 1000000007 取模后的值。

3

5

五种情况如下图所示，颜色只是为了标识不同的积木：

对于所有测试用例，1 ≤ N ≤ 100000001≤N≤10000000.

• 大运行时间：3s
• 大运行内存: 512M

public class Main {
    static final int MOD = 1000000007;
    public static void main(String[] args) {
       Scanner scanner=new Scanner(System.in);
       int n=scanner.nextInt();
            int[][] dp = new int[n + 1][4];
            dp[0][3] = 1;
            for (int i = 1; i<= n; i++) {
                dp[i][0] = dp[i - 1][3];
                dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % MOD;
                dp[i][2] = (dp[i - 1][0] + dp[i - 1][1]) % MOD;
                dp[i][3] = (((dp[i - 1][0] + dp[i - 1][1]) % MOD + dp[i - 1][2]) % MOD + dp[i - 1][3]) % MOD;
            }
            System.out.println(dp[n][3]);
    }
}

多米诺和托米诺平铺，看这道题的解析就行了

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧