题目描述
已知一个数列 a，它满足：
ax={1ax−1+ax−3x∈{1,2,3}x≥4
求 a 数列的第 n 项对 109+7 取余的值。
输入格式
第一行一个整数 T，表示询问个数。
以下 T 行，每行一个正整数 n。
输出格式
每行输出一个非负整数表示答案。
输入输出样例
输入 #1复制
3 6 8 10
输出 #1复制
4 9 19
说明/提示
- 对于 30% 的数据 n≤100；
- 对于 60% 的数据 n≤2×107；
- 对于 100% 的数据 1≤T≤100，1≤n≤2×109。
代码实现：
#include <cstdio> #include <iostream> using namespace std; #define INF 1000000007 long long n, q[105]; struct mat{ long long m[3][3]; int sz; }; mat mul(mat a, mat b) { mat res; for(int i=0;i<3;i++) for(int j=0;j<3;j++) res.m[i][j]=0; for(int i=0;i<3;i++) for(int j=0;j<a.sz;j++) for(int k=0;k<3;k++) res.m[i][j]=((res.m[i][j]%INF)+(a.m[k][j]%INF)*(b.m[i][k]%INF))%INF; res.sz=a.sz; return res; } void qpow(long long x) { mat t, ans; ans.sz=1; t.sz=3; ans.m[0][0]=ans.m[1][0]=ans.m[2][0]=1; for(int i=0;i<3;i++) for(int j=0;j<3;j++) t.m[i][j]=0; t.m[0][0]=t.m[0][2]=t.m[1][0]=t.m[2][1]=1; while(x) { if(x&1) ans=mul(ans, t); t=mul(t, t); x>>=1; } cout<<ans.m[0][0]%INF<<endl; } int main() { cin>>n; for(int i=1;i<=n;i++) cin>>q[i]; for(int i=1;i<=n;i++) { if(q[i]<=3) {cout<<1<<endl;continue;} qpow(q[i]-3); } return 0; }
