首页 > 代码库 > hdu 4549 (矩阵快速幂+费马小定理)
hdu 4549 (矩阵快速幂+费马小定理)
题意:已知F0=a,F1=b,Fn=Fn-1*Fn-2,给你a,b,n求Fn%1000000007的值
思路:我们试着写几组数
F0=a
F1=b
F2=a*b
F3=a*b2
F4=a2*b3
F5=a3*b5
我们发现a,b的系数其实是斐波那契数列,我们只需用矩阵快速幂求出相应系数就行,但是
这个系数随着增长会特别大,这时我们需要利用费马小定理进行降幂处理
费马小定理 ap-1≡1(mod p)
代码:
#include <iostream> #include <cmath> #include <cstdio> #define ll long long #define MOD 1000000007 using namespace std; const int N=2,M=2,P=2; ll qmod(ll a,ll b,ll mod) { ll ans=1; a=a%mod; while(b) { if(b&1) { ans=(ans*a)%mod; } b=b/2; a=(a*a)%mod; } return ans; } struct Matrix { ll m[N][N]; }; Matrix A={1,1, 1,0}; Matrix I={1,0, 0,1}; Matrix mult(Matrix a,Matrix b,ll mod) { Matrix ans; for(int i=0;i<N;i++) { for(int j=0;j<M;j++) { ans.m[i][j]=0; for(int k=0;k<P;k++) { ans.m[i][j]+=(a.m[i][k]*b.m[k][j])%mod; } ans.m[i][j]%=mod; } } return ans; } Matrix power(Matrix a,ll b,ll mod) { Matrix ans=I,p=a; while(b) { if(b&1) { ans=mult(ans,p,mod); } b=b/2; p=mult(p,p,mod); } return ans; } int main() { ll a,b,n; while(cin>>a>>b>>n) { ll aa,bb; Matrix ans=power(A,n-1,MOD-1); bb=ans.m[0][0]; aa=ans.m[1][0]; a=a%MOD; b=b%MOD; if(n==0) bb=0; ll ans1=qmod(a,aa,MOD); ll ans2=qmod(b,bb,MOD); ll num=(ans1*ans2)%MOD; cout<<num<<endl; } return 0; }
hdu 4549 (矩阵快速幂+费马小定理)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。