题解 | #斐波拉契加强版#

class Fibonacci {
     int tmp[2][2], now[2][2];
      inline int addmul(int a, int m0, int m1)
      {
            return (a + (long long) m0 * m1) % 1000000007;
      }
      void mul(int C[][2], int A[][2], int dime)
      {
            int i, j, k;
            memcpy(tmp, C, sizeof (tmp));
            for (i = 0; i < dime; i++)
                  for (j = 0; j < dime; j++)
                  {
                        int t = 0;
                        for (k = 0; k < dime; k++)
                        {
                              t = addmul(t, A[i][k], tmp[k][j]);
                        }
                        C[i][j] = t;
                  }
      }
      void getpow(int res[][2], int mat[][2], int n, int dime)
      {
            memcpy(now, mat, sizeof (now));
            memset(res, 0, sizeof (now));
            for (int i = 0; i < dime; i++)
                  res[i][i] = 1;
            while (n != 0)
            {
                  if (n & 1)
                  {
                        mul(res, now, dime);
                  }
                  n >>= 1;
                  mul(now, tmp, dime);
            }
      }

public:
    int getNthNumber(int n) {
        // write code here
        if(n<2)return 1;
        int res[2][2],A[2][2]={{1,1},{1,0}};
        getpow(res,A,n,2);
        return res[0][0];
    }
};