佛山网站制作网站,wordpress类似娱乐网主题,网页制作专用工具,渠县网站建设上一次我们了解了矩阵的运算和如何使用矩阵解决斐波那契数列#xff0c;这一次我们多看看例题#xff0c;了解什么情况下用矩阵比较合适。
先看例题
1.洛谷P1939 【模板】矩阵加速#xff08;数列#xff09;
模板题应该很简单。 补#xff1a;1n10^9
10^9肯定…上一次我们了解了矩阵的运算和如何使用矩阵解决斐波那契数列这一次我们多看看例题了解什么情况下用矩阵比较合适。
先看例题
1.洛谷P1939 【模板】矩阵加速数列
模板题应该很简单。 补1n10^9
10^9肯定超了所以可以用矩阵做
我们可以观察到每一项x3都是由两个量组成于是创建矩阵 同时
那么因为如果要再让,A*base 之后还是应该是前一个为一项后一项为它的两项前。所以?处应为。??处应为什么自己想想发在评论区里吧。
但是在A中并没有出现这样我们就不可以用A*base表示B了因为矩阵的乘法中必须要上一个矩阵中有的元素才能进入下一个矩阵中。
无论怎样都无法表示为的形式所以B不可以由A构成。
那这个时候就可以用一个巧妙的方法我们在A和B中都增加这一项这样就会变成 可以表示为这样就可以满足每一个条件都可以了。
那么我们利用矩阵乘法在纸上演算七七四十八个小时就可以得出 那么用和斐波那契数列一样的做法快速幂即可
#includebits/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 i0;ia.n;i){for(int j0;jb.m;j){for(int k0;ka.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 i0;ia.n;i)res.a[i][i]1;while(n!0){if(n1){resmul(res,a);}amul(a,a);n1;}return res;
}
long long F(long long n){basebpow(base,n-3);/*for(int i0;i3;i){for(int j0;j3;j){coutbase.a[i][j];}coutendl;}*/ansmul(ans,base);return ans.a[0][0]%mod;
}
int main(){long long t;cint;while(t--){long long n;cinn;if(n3){cout1endl;continue;}init();coutF(n)endl;}return 0;
}2.洛谷P1349 广义斐波那契数列 其实很简单就是把斐波那契数列的模板套一下
先写一半
