3
6
8
10

4
9
19

这道题目可以说是矩阵快速幂中的模板题了。题目中先看到递推式，再看数据范围，很明显告诉你不能在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代码:

#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;
}

最后

以上就是勤劳胡萝卜为你收集整理的UOJ(WHYZ) P14 数列 递推+矩阵快速幂#14. 数列的全部内容，希望文章能够帮你解决UOJ(WHYZ) P14 数列 递推+矩阵快速幂#14. 数列所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。