no cer的一道简单签到题
发布时间: 2017年6月11日 17:59 最后更新: 2017年6月11日 18:10 时间限制: 1000ms 内存限制: 128M
描述
人见人（不）爱，花见花（不）开的nr4强者Cerberux回来啦！
KUCC47XNHC31WC0(CE6KQ.png
他不仅回来了，还带回来了一块2*n的长板。
然而他的蜜汁审美告诉他，这块长板需要贴瓷砖。
但是nr4强者Cerberux只有两种瓷砖，一种是1*2的，一种是1*1的。
他面对这块长板，突然脑抽了，想知道有多少种不同的用1*2和1*1瓷砖填满长板的方案。
大家都知道，nr4强者Cerberux不是一天炼成的。
他为了成为nr4强者，不仅舍弃了上课，拥抱了挂科，还离开了挚爱（个屁）的ACM。
所以他怎么可能会自己动脑想这个和魔方无关的问题。
于是nr4强者Cerberux想问你们有多少种填满长板的方案数？
如果你们回答出来了，将会免费获得由nr4强者Cerberux亲自授课的装x课程1个月（他不给不关我事）。
不同的两种方案必定至少有一个位置填放的瓷砖种类不同或者1*2的瓷砖的方向不同。
输入
第一行一个整数t代表数据组数
每组数据包括一个整数n；
1<=t<=100000
1<=n<=100000
输出
每组数据输出方案数并对1000000007取模，每组数据占一行。
样例输入1 复制
2
2
3
样例输出1
7
22
查看隐藏信息
递推dp
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+100;
long long dp[N+10][5];
const int mod = 1e9+7;
void init()
{
dp[0][3]=1;
for(int i=1;i<=N;i++)
{
dp[i][1]=dp[i-1][3]+dp[i-1][2];
dp[i][2]=dp[i-1][3]+dp[i-1][1];
dp[i][3]=(dp[i-1][1]+dp[i-1][2]+dp[i-1][3]*2+((i==1)?0:dp[i-2][3]))%mod;
}
}
int main()
{
int t;
init();
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
printf("%d\n",dp[n][3] );
}
}