1242 斐波那契数列的第N项(矩阵快速幂）

1242 斐波那契数列的第N项 题目链接：https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1242 斐波那契数列的定义如下： F(0) = 0 F(1) = 1 F(n) = F(n - 1) + F(n - 2) (n >= 2) (1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, ...) 给出n，求F(n)，由于结果很大，输出F(n) % 1000000009的结果即可。 Input 输入1个数n(1 <= n <= 10^18)。 Output 输出F(n) % 1000000009的结果。 Input示例 11 Output示例 89 代码#include<stdio.h>   #include<string.h>   #include<iostream> using namespace std; struct node   {     __int64 mat[15][15];   };//矩阵型结构体   __int64 n,inf=10e9+9;   node mat_mat(node a,node b)//矩阵乘法   {     node c;      for(int i=0;i<=1;i++)          {                  for(int j=0;j<=1;j++)                  {                  c.mat[i][j]=0;                        for(int k=0;k<=1;k++)                          {                                  c.mat[i][j]+=a.mat[i][k]*b.mat[k][j];                                  c.mat[i][j]%=inf;                          }                  }          }     return c;   }        node pow(node a,__int64 nn)   {      node aa;      aa=a;     nn--;     while(nn)      {        if(nn&1)        aa=mat_mat(a,aa);        a=mat_mat(a,a);        nn>>=1;      }      return aa;   }   int main ()   {     node a,b;     __int64 sum,n;        scanf("%I64d",&n);  if(n==0) { printf("0\n"); return 0; } if(n==1) { printf("1\n"); return 0; }     a.mat[0][0]=a.mat[0][1]=a.mat[1][0]=1;     a.mat[1][1]=0;      b=pow(a,n-1);        sum=b.mat[0][0]%inf;      printf("%I64d\n",sum);      return 0;   }