UOJ(WHYZ) P14 数列递推+矩阵快速幂#14. 数列

100 阅读 0 评论 66 点赞

我是靠谱客的博主勤劳胡萝卜，这篇文章主要介绍UOJ(WHYZ) P14 数列递推+矩阵快速幂#14. 数列，现在分享给大家，希望可以做个参考。

#14. 数列

题目描述

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

求a

数列的第 n 项对 1000000007 取余的值。

输入描述第一行一个整数T，表示询问个数。

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

输出描述

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

样例输入

复制代码

样例输出

复制代码

时间限制、数据范围及描述

时间：1s 空间：256M

n<=2*10^9

题目链接

这道题目可以说是矩阵快速幂中的模板题了。题目中先看到递推式，再看数据范围，很明显告诉你不能在O（n）时间内完成。因此我们考虑矩阵快速幂的算法。在这道题目中，我们至少只需要保留f[n-1]和f[n-3]两个值就能推出f[n]，但因为f[n+1]需要用到f[n-2]的值，所以我们在矩阵中也必须保留。这样，我们便能推出解题的矩阵{{1,0,1},{1,0,0},{0,1,0}}，再运用矩阵快速幂即可在logn时间内完成。

AC代码:

复制代码

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
#include<cstdio>
#include<iostream>
#include<cstring>
#define ll long long
using namespace std;
const int mod=1000000007;
struct jz{
	ll x[5][5];
};
jz mult(jz a,jz b){
	jz c;
	memset(c.x,0,sizeof(c.x));
	for(int i=0;i<3;i++){
		for(int j=0;j<3;j++){
			for(int k=0;k<3;k++){
				c.x[i][j]=(c.x[i][j]+a.x[i][k]*b.x[k][j])%mod; 
			}
		}
	}
	return c;
}
jz qpow(jz m,int n){
	jz mul={{1,0,0,1}};
	while(n){
		if(n&1){
			mul=mult(mul,m);
		}
		n>>=1;
		m=mult(m,m);
	} 
	return mul;
}
int main(){
	int n,t;
	scanf("%d",&t);
	while(t--){
		jz m,ans;
		m.x[0][0]=m.x[0][2]=m.x[1][0]=m.x[2][1]=1;
		m.x[0][1]=m.x[1][1]=m.x[1][2]=m.x[2][2]=m.x[2][0]=0;
		scanf("%d",&n);
		ans=qpow(m,n-1);
		printf("%dn",ans.x[0][0]);
	}
	return 0;
}