上海计算机学会2021年12月月赛C++乙组T1四铺地砖
发布时间
阅读量：
阅读量
题目描述
一条道路需要用地砖进行铺设工作。这条路段由n乘以二个方格构成，在铺设过程中需要用到两种不同规格的地砖——一种是长度为一宽为二的类型（即每块可覆盖相邻的两个方格），另一种则为正方形大小（尺寸为二乘二）。由于这两种类型的瓷砖都有足够的供应量可用，请问有多少种不同的铺设方式能够满足整个路段的要求。
由于方案数可能很大，输出它模 1,000,000,007 的余数即可。
输入格式
单个整数：表示 n。
输出格式
单个整数：表示方案数模 1,000,000,007 的余数。
数据范围
- 对于 30% 的数据，1≤n≤15；
- 对于 70% 的数据，1≤n≤50000；
- 对于 100% 的数据，1≤n≤100000。
样例数据
输入:
2
输出:
3
输入:
8
输出:
171
此题可采用递推法来解决
所以a[i] = (a[i - 1] + 2 * a[i - 2])
详见代码：
#include <bits/stdc++.h>
using namespace std;
long long a[100005];
int main() {
int n;
cin >> n;
a[1] = 1;
a[2] = 3;
for (int i = 3; i <= n; i++) {
a[i] = (a[i - 1] + 2 * a[i - 2]) % (1000000007);
}
cout << a[n] << endl;
return 0;
}全部评论 (0)
还没有任何评论哟~