《P1939 矩阵加速（数列）》

题目描述

已知一个数列 a，它满足：

ax​={1ax−1​+ax−3​​x∈{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; }