AHSOFNU NOIP模拟题-2 T2(矩阵快速幂)

这里直接递推肯定炸。
我们根据
$$F_{n} = F_{n-1} +F_{n-3}$$
构造矩阵
$$
\begin{pmatrix}
1 & 0 & 1\\\
1 & 0 & 0\\\
0 & 1 & 0
\end{pmatrix}
\times
\begin{pmatrix}
F_{n-1} \\\
F_{n-2} \\\
F_{n-3}
\end{pmatrix}
=
\begin{pmatrix}
F_{n} \\\
F_{n-1} \\\
F_{n-2}
\end{pmatrix}
$$
矩阵快速幂即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define FN2 "seq"
using namespace std;
const int MAXN = 6, MO = 1000000007;
struct matrix {
int x, y;
LL ma[MAXN][MAXN];
void init(int x, int y) {this->x = x, this->y = y; for (int i=0;i<MAXN;i++) for (int j=0;j<MAXN;j++) ma[i][j] = (i==j);}
void init2(int x, int y) {this->x = x, this->y = y; for (int i=0;i<MAXN;i++) for (int j=0;j<MAXN;j++) ma[i][j] = 0;}
}a;
int n;
matrix mul(matrix ai, matrix bi) {
matrix ret;
ret.init2(3, 3);
for (int i=0;i<ai.x;i++)
for (int j=0;j<bi.y;j++)
for (int k=0;k<ai.y;k++) ret.ma[i][j] = (ret.ma[i][j]+(ai.ma[i][k]*bi.ma[k][j])%MO)%MO;
return ret;
}
matrix poww(matrix ai, int x) {
matrix ret, s = ai;
ret.init(3, 3);
while (x) {
if (x&1) ret = mul(ret, s);
s = mul(s, s);
x>>=1;
}
return ret;
}
void clean() {}
void solve() {
clean();
scanf("%d", &n);
if (n<=3) {printf("1\n"); return ;}
a.init2(3, 3), a.ma[0][0] = 1, a.ma[0][2] = 1, a.ma[1][0] = 1, a.ma[2][1] = 1;
matrix b = poww(a, n-1);
printf("%lld\n", b.ma[0][0]);
}
int main() {
freopen(FN2".in", "r", stdin); freopen(FN2".out", "w", stdout);
int T; scanf("%d", &T);
while (T--) solve();
fclose(stdin); fclose(stdout);
return 0;
}

Problem 2 数列(seq.cpp/c/pas)
【题目描述】
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;

------ 本文结束 ------