/*
问题描述
已知递推公式：
F(n, 1)=F(n-1, 2) + 2F(n-3, 1) + 5,
F(n, 2)=F(n-1, 1) + 3F(n-3, 1) + 2F(n-3, 2) + 3.
初始值为：F(1, 1)=2, F(1, 2)=3, F(2, 1)=1, F(2, 2)=4, F(3, 1)=6, F(3, 2)=5。
输入n，输出F(n, 1)和F(n, 2)，由于答案可能很大，你只需要输出答案除以99999999的余数。
输入格式
输入第一行包含一个整数n。
输出格式
输出两行，第一行为F(n, 1)除以99999999的余数，第二行为F(n, 2)除以99999999的余数。
样例输入
4
样例输出
14
21
数据规模和约定
1<=n<=10^18
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=99999999;
struct matrix
{
ll a[8][8];
};
matrix multiply(matrix x,matrix y,int m,int n,int s)
{
matrix tmp;
memset(tmp.a,0,sizeof(tmp.a));
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
for(int k=0;k<s;k++){
tmp.a[i][j]=(tmp.a[i][j] + (x.a[i][k] * y.a[k][j])%mod)%mod;
}
}
}
return tmp;
}
matrix tmp={
0,1,1,0,0,0,0,0,
1,0,0,1,0,0,0,0,
0,0,0,0,1,0,0,0,
0,0,0,0,0,1,0,0,
2,3,0,0,0,0,0,0,
0,2,0,0,0,0,0,0,
1,0,0,0,0,0,1,0,
0,1,0,0,0,0,0,1
};
int main()
{
matrix res;
ll f[8]={6,5,1,4,2,3,5,3};
ll sum1,sum2,n;
memset(res.a,0,sizeof(res.a));
for(int i=0;i<8;i++){
res.a[i][i]=1;
}
cin>>n;
if(n==1)
cout<<"2"<<endl<<"3"<<endl;
if(n==2)
cout<<"1"<<endl<<"4"<<endl;
if(n==3)
cout<<"6"<<endl<<"5"<<endl;
if(n>=4){
n-=3;
while(n) //矩阵快速幂
{
if(n&1) res=multiply(res,tmp,8,8,8);
//&是位与操作符，n&1,不将n的二进制形式与00000000 00000001按位做与操作。这时，只 //要//n的最右边一位是1，结果就不是0，为true，条件成立。所以这句话实际上就是if(n%2==1)
n>>=1;
tmp=multiply(tmp,tmp,8,8,8);
}
sum1=0;
sum2=0;
for(int i=0;i<8;i++)
{
sum1=(sum1+(f[i]*res.a[i][0])%mod)%mod;
sum2=(sum2+(f[i]*res.a[i][1])%mod)%mod;
}
cout<<sum1<<endl;
cout<<sum2<<endl;
}
return 0;
}
请问其中的f[]究竟是如何求出来的，他到底是什么意思
http://www.cnblogs.com/yan-boy/archive/2012/11/29/2795294.html