博客

对于一个 22 行 NN 列的走道。现在用 1 \times 2, 2 \times 21×2,2×2 的砖去铺满。问有多少种不同的方式。

下图是一个 22 行 1717 列的走道的某种铺法。

输入格式

一个数字 NN，0 \le n \le 2500≤n≤250。

输出格式

方案数。（对 100007100007 取模）。

输出时每行末尾的多余空格，不影响答案正确性

样例输入1复制

2

样例输出1复制

3

样例输入2复制

8

样例输出2复制

171

#include <bits/stdc++.h>
#define pb push_back
#define mem(a,b) memset(a,b,sizeof a)
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
int main()
{
//	freopen("D:\\LYJ.txt","r",stdin);
	int n,mmap[255]={0,1,3,5};
	cin>>n;
	if(n<=3) cout<<mmap[n];
	else
	{
		for(int i=4;i<=n;i++)
		{
			mmap[i]=(mmap[i-1]+2*mmap[i-2])%100007;
		}
		cout<<mmap[n];
	}
	return 0;
}