ZJ b525 先別管這個了，你聽過turtlebee嗎？

ZJ b525  先別管這個了，你聽過turtlebee嗎？

題目概述:

turtlebee是一種神秘的生物。傳聞中turtlebee可以根據服裝改變自己的性別，如果穿男裝就會是雄性，穿女裝就會是雌性。傳說turtlebee有很強的生育能力，一隻女裝turtlebee過一天後就會生出一隻新的男裝turtlebee。而男裝turtlebee過一天後就會換上女裝，而且不會再換回來。你知道現在有幾隻男裝turtlebee及幾隻女裝turtlebee，問你k天后會有幾隻turtlebee。

思路:

枚舉出來會發現好像很類似費式數列之類的東西。

數字非常大，不能用O(n)解。

可以利用矩陣快速冪!!

AC code:

//By SCJ

#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

#define MOD 100000007

typedef long long ll;

typedef vector<ll> vec;

typedef vector<vec> mat;

mat mul(mat &A,mat &B)

{

   mat C((int)A.size(),vec((int)B[0].size()));

   for(int i=0;i<A.size();++i)

       for(int j=0;j<B[0].size();++j)

           for(int k=0;k<B.size();++k)

               C[i][j]=(C[i][j]+A[i][k]*B[k][j]%MOD)%MOD;

   return C;

}

mat POW(mat A,ll n)

{

   mat res(A.size(),vec(A.size()));

   for(int i=0;i<A.size();++i) res[i][i]=1;

   mat base=A;

   while(n)

   {

       if(n&1) res=mul(base,res);

       base=mul(base,base);

       n>>=1;

   }

   return res;

}

int main()

{

ios::sync_with_stdio(0);

cin.tie(0);

   ll a,b,c;

   mat P(2,vec(2));

   P[0][0]=0;

   P[0][1]=P[1][0]=P[1][1]=1;

   while(cin>>a>>b>>c)

   {

       mat A(2,vec(1));

       A[0][0]=a;

       A[1][0]=b;

       mat tp=POW(P,c);

       mat ans=mul( tp , A );

       cout<<(ans[0][0]+ans[1][0])%MOD<<endl;

   }

}