POJ 3734 Blocks——矩阵快速幂

POJ 3734 Blocks——矩阵快速幂

挑战程序设计P203，重点是求递推式

#include #include #include #include using namespace std;const int maxn = 5;const int mod = 10007;int T, n;struct Matrix { int mat[maxn][maxn]; Matrix() { memset(mat, 0, sizeof(mat)); } Matrix operator * (const Matrix& x) const { Matrix ans; for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { for (int k = 0; k < 3; k++) { ans.mat[i][j] = (ans.mat[i][j] + mat[i][k] * x.mat[k][j]) % mod; } } } return ans; }};Matrix mpow(Matrix& a, int x) { Matrix ans; for (int i = 0; i < 3; i++) ans.mat[i][i] = 1; while (x) { if (x & 1) ans = ans * a; a = a * a; x >>= 1; } return ans;}int main() { scanf("%d", &T); while (T--) { scanf("%d", &n); Matrix a; a.mat[0][0] = 2; a.mat[0][1] = 1; a.mat[0][2] = 0; a.mat[1][0] = 2; a.mat[1][1] = 2; a.mat[1][2] = 2; a.mat[2][0] = 0; a.mat[2][1] = 1; a.mat[2][2] = 2; a = mpow(a, n); printf("%d\n", a.mat[0][0]); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。