当前位置：首页 > news >正文

免费域名注册网站源码湖北城乡住房建设厅网站

news 2025/11/6 10:14:16

免费域名注册网站源码,湖北城乡住房建设厅网站,巅云建站,医院网站建设要求是什么上一次我们了解了矩阵的运算和如何使用矩阵解决斐波那契数列，这一次我们多看看例题，了解什么情况下用矩阵比较合适。先看例题 1.洛谷P1939 【模板】矩阵加速（数列） 模板题应该很简单。补：1<n<10^9 10^9肯定…

上一次我们了解了矩阵的运算和如何使用矩阵解决斐波那契数列，这一次我们多看看例题，了解什么情况下用矩阵比较合适。

先看例题

1.洛谷P1939 【模板】矩阵加速（数列）

模板题应该很简单。

补：1<n<=10^9

10^9肯定超了，所以可以用矩阵做

我们可以观察到，每一项（x>3）都是由两个量组成，于是创建矩阵：

$A=[a_{n-1},a_{n-3}]$

同时： $B=A\times base=[a_{n},?]$

那么因为如果要再让 $A\times base\times base=[a_{n+1},??]$ ,A*base 之后还是应该是前一个为一项，后一项为它的两项前。所以?处应为 $a_{n-2}$ 。??处应为什么自己想想，发在评论区里吧。

但是， $a_{n-2}$ 在A中并没有出现，这样我们就不可以用A*base表示B了，因为矩阵的乘法中，必须要上一个矩阵中有的元素，才能进入下一个矩阵中。

无论怎样， $a_{n-2}$ 都无法表示为 $n\times a_{n-1}+m\times a_{n-2}$ 的形式，所以B不可以由A构成。

那这个时候就可以用一个巧妙的方法：我们在A和B中都增加 $a_{n-2}$ 这一项，这样就会变成

$[a_{n-1},a_{n-2},a_{n-3}]\times base=[a_{n},a_{n-1},a_{n-2}]$

$a_{n}$ 可以表示为 $a_{n-1}+a_{n-3}$ ，这样就可以满足每一个条件都可以了。

那么我们利用矩阵乘法，在纸上演算七七四十八个小时，就可以得出，

$base=\begin{bmatrix} 1,1,0\\ 0,0,1\\ 1,0,0\\ \end{bmatrix}$

那么用和斐波那契数列一样的做法，快速幂即可

#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
struct Matrix{int n,m;long long a[100][100];Matrix(){memset(a,0,sizeof(a));}Matrix(int _n,int _m){n=_n;m=_m;memset(a,0,sizeof(a));}
};
Matrix ans(1,3);
Matrix base(3,3);
void init(){ans.a[0][0]=1;ans.a[0][1]=1;ans.a[0][2]=1;base.a[0][0]=1;base.a[0][1]=1;base.a[0][2]=0;base.a[1][0]=0;base.a[1][1]=0;base.a[1][2]=1;base.a[2][0]=1;base.a[2][1]=0;base.a[2][2]=0;
}
Matrix mul(Matrix a,Matrix b){Matrix res(a.n,b.m);for(int i=0;i<a.n;i++){for(int j=0;j<b.m;j++){for(int k=0;k<a.m;k++){res.a[i][j]+=a.a[i][k]*b.a[k][j]%mod;}res.a[i][j]%=mod;}}return res;
}
Matrix bpow(Matrix a,long long n){Matrix res(a.n,a.n);for(int i=0;i<a.n;i++)res.a[i][i]=1;while(n!=0){if(n&1){res=mul(res,a);}a=mul(a,a);n>>=1;}return res;
}
long long F(long long n){base=bpow(base,n-3);/*for(int i=0;i<3;i++){for(int j=0;j<3;j++){cout<<base.a[i][j];}cout<<endl;}*/ans=mul(ans,base);return ans.a[0][0]%mod;
}
int main(){long long t;cin>>t;while(t--){long long n;cin>>n;if(n<=3){cout<<1<<endl;continue;}init();cout<<F(n)<<endl;}return 0;
}