A40903. 格子刷油漆
填空题
困难
知识点
题目描述
格子刷油漆
题目描述
X国的一段古城墙的顶端可以看成 2×N个格子组成的矩形（如下图所示），现需要把这些格子刷上保护漆。
例如下图是一个长度为3，高为2的城墙
你可以从任意一个格子刷起，刷完一格，可以移动到和它相邻的格子（对角相邻也算数），但不能移动到较远的格子（因为油漆未干不能踩！）
比如：
a d b c e f 就是合格的刷漆顺序。
c e f d a b 是另一种合适的方案。
当已知 N 时，求总的方案数。当n较大时，结果会迅速增大，请把结果对 1000000007 (十亿零七) 取模。
输入格式：输入数据为一个正整数（不大于1000）
输出格式：输出数据为一个正整数。
样例输入：2 样例输出：24
样例输入：3 样例输出：96
样例输入：22 样例输出：359635897
参考答案
#include<iostream>
using namespace std;
const int MOD=1000000007;
int main()
{
int n; cin>>n;
long long a[1005],b[1005];
if(n==1){
cout<<2<<endl;
return 0;
}
// 赋初值
a[1]=1,a[2]=6;
b[1]=1,b[2]=2;
// 打表，递推求出a数组和b数组在不同长度情况下的值=
for(int i=3;i<=n;i++)
{
b[i]=(2*b[i-1])%MOD;
a[i]=(2*a[i-1]+b[i]+4*a[i-2])%MOD;
}
// 4个顶点
// 特别注意这里sum的数据类型需要用long long，否则有可能在乘以4后发生数据溢出
long long sum=4*a[n] % MOD;
// 根据前面算出的a[ ]数组和b[ ]数组，递推出从中间出发时的方案数
// 注意i的范围是大于1小于n
for(int i=2;i<n;i++)
sum = (sum+4*(b[i]*a[n-i]+b[n-i+1]*a[i-1]))%MOD;
cout<<sum<<endl;
return 0;
}
上一题
下一题