传送门
k <= 109 暴力肯定超时
根据矩阵性质，可以发现
S(4) = A1 + A2 + A2* (A1 + A2)
S(5) = A1 + A2 +A2* (A1+ A2) + A5
所以可以递归二分求解，分别判断 Ak，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
上一篇：[luoguP2982][USACO10FEB]慢下来Slowing down（dfs序 + 线段树）
下一篇：[HDU2196]Computer（DP）
二分 矩阵
