矩阵快速幂优化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 0class Solution {
public:int climbStairs(int n) {// f(1) = 1 f(2) = 2if (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];}
};