「NOIP模拟赛」数列

2014年5月10日2,1064

「题目描述」

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
aiyoupass
aiyoupass

我不是很明白是怎么构造的矩阵, 不过我自己构造了一个
$$\begin{bmatrix}
1\ 0\ 1\\
1\ 0\ 0\\
0\ 1\ 0\\
\end{bmatrix}\times
\begin{bmatrix}
a_{x-1}\\
a_{x-2}\\
a_{x-3}\\
\end{bmatrix}=
\begin{bmatrix}
a_{x}\\
a_{x-1}\\
a_{x-2}\\
\end{bmatrix}
$$
不知道这么做对不对

黑暗世界

分段打表才是王道

Mektpoy

是强啊