递推覆盖墙壁

覆盖墙壁

题目描述

你有一个长为N宽为2的墙壁，给你两种砖头：一个长2宽1，另一个是 L 型覆盖3个单元的砖头。如下图：

1
2
0  0
0  00

砖头可以旋转，两种砖头可以无限制提供。你的任务是计算用这两种来覆盖N2的墙壁的覆盖方法。例如一个23的墙可以有5种覆盖方法，如下：

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

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

1
2
0112
0012

给定N，要求计算2N的墙壁的覆盖方法。由于结果很大，所以只要求输出最后4位。例如213 的覆盖方法为13465，只需输出3465即可。如果答案少于4位，就直接输出就可以，不用加前导0，如N=3时输出5。

输入格式

一个整数N，表示墙壁的长。

输出格式

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

样例 #1

样例输入 #1

1
13

样例输出 #1

1
3465

提示

数据保证1< N< 1000000。

讲解视频https://www.bilibili.com/video/BV1aL4y1A7Kz/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
#include<bits/stdc++.h> 
using namespace std; 
const int maxn=1000002;//const定义的变量,是告诉系统,这个变量不能改
const int mod=10000;
int f[maxn],g[maxn];
 
int main()
{
	int n;
	cin>>n;
	f[0]=1;
	f[1]=g[1]=1;
	for(int i=2;i<=n;i++){
		f[i]=((f[i-1]+f[i-2])%mod+2*g[i-2]%mod)%mod;
		g[i]=(g[i-1]+f[i-1])%mod;
	}
	
	cout<<f[n];
	return 0;
}