M斐波那契数列

M斐波那契数列F[n]是一种整数数列，它的定义如下： F[0] = a F[1] = b F[n] = F[n-1] * F[n-2] ( n > 1 ) 现在给出a, b, n，你能求出F[n]的值吗？ Input 输入包含多组测试数据； 每组数据占一行，包含3个整数a, b, n（ 0 <= a, b, n <= 10^9 ） Output 对每组测试数据请输出一个整数F[n]，由于F[n]可能很大，你只需输出F[n]对1000000007取模后的值即可，每组数据输出一行。 Sample Input 0 1 0 6 10 2 Sample Output 0 60

现在还是一知半解，所以还是先记录下来，以后我们再去细细的分析。主要是，我们以后要穿送指针的话，我们就把他包装成结构体，直接传送结构体，不要传送指针。

#include <bits/stdc++.h> using namespace std; typedef long long ll; ll mod = 1e9+7; ll mod2 = 1e9+6; struct matrix{ ll base[2][2]; }; struct matrix multi( struct matrix a,struct matrix b ){ struct matrix ans; memset(ans.base,0,sizeof(ans.base)); for(int i=0; i<2; i++){ for(int j=0; j<2; j++){ for(int k=0; k<2; k++){ ans.base[i][j] = (ans.base[i][j] + (a.base[i][k]*b.base[k][j])%mod2)%mod2; } } } return ans; } struct matrix quick_pow(struct matrix a,ll m){ struct matrix ans; ans.base[0][0] = ans.base[1][1] = 1; ans.base[0][1] = ans.base[1][0] = 0; while( m ){ if( m&1 ) ans = multi(ans,a); m >>= 1; a = multi(a,a); } return ans; } ll quickint_pow(ll a,ll m){ ll ans = 1; while( m ){ if( m&1 ) ans = (ans*a)%mod; m >>= 1; a = (a*a)%mod; } return ans; } int main(){ ll a,b,n; struct matrix aa,ans; aa.base[0][0] = aa.base[0][1] = aa.base[1][0] = 1; aa.base[1][1] = 0; while( cin >> a >> b >> n ){ if( n==0 ){ cout << a << endl; continue; } ans = quick_pow(aa,n-1); cout << ( quickint_pow(a,ans.base[0][1]) * quickint_pow(b,ans.base[0][0]) )%mod << endl; } return 0; }