斐波那契数列的N项（矩阵快速幂）

题目：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1242

#include<iostream>
#include<cstring>
using namespace std;
const int m=1e9+9;
struct mat
{
    __int64 p[3][3];
};

mat mat_mul(mat a,mat b)
{
    mat c;
    
    memset(c.p,0,sizeof(c.p));
    for(int i=1;i<=2;i++)
        for(int j=1;j<=2;j++)
            for(int r=1;r<=2;r++)
            {
                c.p[i][j]+=a.p[i][r]*b.p[r][j];
                c.p[i][j]%=m;
            }
                
    return c;
}

void mat_pow(__int64 n)
{
    mat ans,c;
    __int64 t;
    
    t=n-1;
    memset(ans.p,0,sizeof(ans.p));
    memset(c.p,0,sizeof(c.p));
    ans.p[1][1]=1;
    ans.p[2][1]=0;
    c.p[1][1]=c.p[1][2]=c.p[2][1]=1;
    c.p[2][2]=0;
    
    while(t)
    {
        if(t&1)
            ans=mat_mul(ans,c);
        c=mat_mul(c,c);
        t=t>>1;
    }
    cout<<ans.p[1][1];
}
int main()
{
    __int64 n;
    
    cin>>n;
    mat_pow(n);
}