[POJ3233] Matrix Power Series（矩阵快速幂）

传送门

k <= 10⁹ 暴力肯定超时

根据矩阵性质，可以发现

S(4) = A¹ + A² + A²* (A¹ + A²)

S(5) = A¹ + A² +A²* (A¹+ A²) + A⁵

所以可以递归二分求解，分别判断 A^k，k 为奇数和偶数的情况

——代码

1 #include <cstdio> 2 #include <cstring> 3 4 struct Matrix 5 11 }; 12 13 int n, k, p; 14 Matrix I, P; 15 16 inline Matrix operator * (const Matrix x, const Matrix y) 17 26 27 inline Matrix operator + (const Matrix x, const Matrix y) 28 36 37 inline Matrix operator ^ (Matrix x, int y) 38 46 return ans; 47 } 48 49 inline Matrix work(Matrix x, int y) 50 57 58 int main() 59 74 } 75 return 0; 76 }
View Code

上一篇：[BZOJ2462] [BeiJing2011]矩阵模板（二维Hash）

下一篇：[luoguP1970] 花匠（DP）

---

二分 矩阵