P1337 fibonacci数列（tyvj）

/*
  根据分析可以得到ans{f(n-1),f(n)}*k{0,1}=ans{f(n),f(n+1)}
                             {1,1}  
  那么由ans{f(1),f(2)}到ans{f(n-1),f(n)},需乘以n-1个k矩阵，这是可以应用快速幂求的 
*/ 


#include<cstdio>
#include<iostream>
#define m 32768
#define N 2
using namespace std;

struct mat
{
    int num[N][N];
}k,ans;
int n;

mat work(mat a,mat b)//矩阵乘法 
{
    mat temp;
    for (int i=0;i<N;i++)
      for (int j=0;j<N;j++)
        temp.num[i][j]=0;
    for (int i=0;i<N;i++)
      for (int j=0;j<N;j++)
      {
        for (int h=0;h<N;h++)
          temp.num[i][j]+=a.num[i][h]*b.num[j][h];
          temp.num[i][j]%=m;
      }
    return temp;
}

void power()//快速幂 
{
    while (n!=0)
      {
           if (n%2==1) ans=work(ans,k);
           k=work(k,k);
           n/=2;
      }
}


int main()
{
    scanf("%d",&n);
    n=n-2;
    k.num[0][0]=0;
    k.num[0][1]=k.num[1][0]=k.num[1][1]=1;
    ans.num[0][0]=ans.num[0][1]=1;
    ans.num[1][0]=ans.num[1][1]=0;
    power();
    printf("%d",ans.num[0][1]);
}