矩阵快速幂优化dp

之前一直想找一个矩阵快速幂的专题，但是都没有题目来总结，今天就来水一下

这个题目的转移方程我们可以很快想出来，但是我们如何作为我们矩阵快速幂的敲门砖呢？

有一个问题要注意的是我们由于这题不是取模的，可能会溢出，我们要开 long long 才行

class Ma { public:     int a[2][2];     Ma() {         memset(a, 0, sizeof a);     }     friend Ma operator*(Ma b, Ma c) {         Ma d;         for (int i = 0; i < 2; i++) {             for (int j = 0; j < 2; j++) {                 for (int k = 0; k < 2; k++) {                     d.a[i][j] += b.a[i][k] * c.a[k][j];                 }             }         }return d;     } };  // 1 1 // 1 0      class Solution { public:     int climbStairs(int n) {         // f(1) = 1 f(2) = 2         if (n == 1) return 1; if (n == 2) return 2;         Ma b; b.a[0][0] = 2; b.a[1][0] = 1;         n -= 2; Ma c;         c.a[0][0] = c.a[1][0] = c.a[0][1] = 1;         while (n) {             if (n & 1) b = b* c;             c = c * c;             n >>= 1;         }         return b.a[0][0];     } };