【NOIP模拟赛】数列

2014年5月10日1,0263

【题目描述】

a[1]=a[2]=a[3]=1

a[x]=a[x-3]+a[x-1]  (x>3)

求a数列的第n项对1000000007(10^9+7)取余的值。

【输入格式】

第一行一个整数T,表示询问个数。

以下T行,每行一个正整数n。

【输出格式】

每行输出一个非负整数表示答案。

【样例输入】

3

6

8

10

【样例输出】

4

9

19

【数据范围】

对于30%的数据 n<=100;

对于60%的数据 n<=2*10^7;

对于100%的数据 T<=100,n<=2*10^9;

题解

这个可以直接矩阵乘法搞掉。。