「NOIP模拟赛」数列

2014年5月10日4,0123

「题目描述」

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;

题解

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

 

avatar
1 Comment threads
2 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
2 Comment authors
Mektpoyhzwer黑暗世界 Recent comment authors
  Subscribe  
提醒
黑暗世界

分段打表才是王道

Mektpoy

是强啊