上海计算机学会2024年1月月赛C++丙组T3三排地砖
发布时间
阅读量：
阅读量
三排地砖
内存限制: 256 Mb时间限制: 1000 ms
题目描述
有一条道路需要铺设地砖，这条道路由 n×3 个方格组成。只有一种规格的地砖，大小是 1×2 规格的，也就是恰好可以覆盖两个方格。请计算有多少种方法，将这条道路铺满地砖。
由于方案数可能很大，输出它模 1,000,000,007 的余数即可。
输入格式
- 单个整数：表示 n。(保证n为偶数)
输出格式
- 单个整数：表示方案数模 1,000,000,007 的余数。
数据范围
- 对于 30% 的数据，1≤n≤15；
- 对于 70% 的数据，1≤n≤300；
- 对于 100% 的数据，1≤n≤200000。
样例数据
输入:
2
输出:
3
输入:
8
输出:
153
解析：使用递推算法。
对于分界线在1的a[1]有两种情况：
对于分界线在2的a[2]有三种情况：
对于分界线在3的a[3]，由a[1]接过来的方案有a[1]种：
由a[2]接过来的有a[2]*2种：则a[3]=a[1]+a[2]*2
对于边界在4的a[4]，由a[1]接过来的有a[1]种：
由a[2]接过来的有a[2]*3种：则a[4]=a[1]+a[2]*3;
分析得出递推关系式：
对于i为奇数 a[i]=a[i-1]*2+a[i-2];
对于i为偶数 a[i]=a[i-2]*3+a[i-3];
详见代码：
#include<bits/stdc++.h>
using namespace std;
int n;
long long a[200005];
int mod = 1000000007;
int main() {
cin >> n;
a[2] = 3;
a[1] = 2;
for(int i = 3; i <= n; i++) {
if (i % 2 == 1) {
a[i] = a[i - 1] * 2 + a[i - 2];
} else {
a[i] = a[i - 2] * 3 + a[i - 3];
}
a[i] %= mod;
}
cout << a[n];
return 0;
}
全部评论 (0)
还没有任何评论哟~