题目描述

你有一个长为 nn 宽为 22 的墙壁，给你两种砖头：一个长 22 宽 11，另一个是L型覆盖 33 个单元的砖头。如下图：

1
2
0  0
0  00

砖头可以旋转，两种砖头可以无限制提供。你的任务是计算用这两种来覆盖 2×n2\times n 的墙壁的覆盖方法。例如一个 2×32\times 3 的墙可以有 55 种覆盖方法，如下：

1
2
012 002 011 001 011  
012 112 022 011 001

注意可以使用两种砖头混合起来覆盖，如 2×42\times 4 的墙可以这样覆盖：

1
2
0112
0012

给定 nn，要求计算 2×n2\times n的墙壁的覆盖方法。由于结果很大，所以只要求输出最后 44 位。例如 2×132\times 13 的覆盖方法为 1346513465，只需输出 34653465 即可。如果答案少于 44 位，就直接输出就可以，不用加 00，如 n=3n=3，时输出 55。

输入格式

一个整数 nn（1≤n≤10000001\le n\le 1000000），表示墙壁的长。

输出格式

输出覆盖方法的最后 44 位，如果不足 44 位就输出整个答案。

输入输出样例

输入 #1

1
13

输出 #1

1
3465

思路

设 fnf_n 表示覆盖 2×n2\times n 墙壁的方案数。边界条件为 f0=1f_0=1，即什么都不放。

考虑最后一步放什么样的砖块：

  • 若竖放一个 2×12\times 1 的砖块，则方案数为 fn−1f_{n-1}；
  • 若横放一个 2×12\times 1 的砖块，则倒数第二步也必须是横放一个 2×12\times 1 的砖块，则方案数为 fn−2f_{n-2}；
  • 若放一个L型砖块（因为该砖块可以翻转着放，所以这样放的总方案数要乘 22），会带来一个格子的空缺，需要填补这个空缺，
    • 再放一个L型砖块，正好填补这个空缺，方案数为 fn−3f_{n-3}，
    • 依次横放 2×12\times 1 的砖块，再放一个L型砖块，方案数为 fn−4+fn−5+⋯+f0f_{n-4}+f_{n-5}+\cdots+f_0，
    • 因此最后放一个L型砖块的方案数为 2×∑i=n−30fi2\times\sum\limits_{i=n-3}^0 f_i；

图示

总方案数为 fn=fn−1+fn−2+2×∑i=n−30fif_n=f_{n-1}+f_{n-2}+2\times \sum\limits_{i=n-3}^0 f_i，故 fn−1=fn−2+fn−3+2×∑i=n−40fif_{n-1}=f_{n-2}+f_{n-3}+2\times\sum\limits_{i=n-4}^0f_i，可得 fn=2×fn−1+fn−3f_{n}=2\times f_{n-1}+f_{n-3}。

（以上部分参考洛谷题解）

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: Luogu P1990
Date: 2021 Apr. 2nd
Description: Recursion
*******************************************************************/
#include<iostream>
using namespace std;
const int N = 1000000;
const int MOD = 10000;
int f[N + 1];
int main() {
	f[0] = 1;
	f[1] = 1;
	f[2] = 2;
	f[3] = 5;
	for (int i = 2; i <= N; i++) {
		f[i] = (2 * f[i - 1] + f[i - 3]) % 10000;
	}
	int n;
	cin >> n;
	cout << f[n] << endl;
	return 0;
}