首页 > 代码库 > HDU1575-Tr A(矩阵快速幂)
HDU1575-Tr A(矩阵快速幂)
题目链接
题意:A为一个方阵,则Tr A表示A的迹(就是主对角线上各项的和),现要求Tr(A^k)%9973。
思路:简单的矩阵快速幂
代码:
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> using namespace std; //typedef long long ll; typedef __int64 ll; const int MOD = 9973; const int N = 15; ll k; int n; struct mat{ int s[N][N]; mat() { memset(s, 0, sizeof(s)); } mat operator * (const mat& c) { mat ans; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) for (int k = 0; k < N; k++) ans.s[i][j] = (ans.s[i][j] + s[i][k] * c.s[k][j]) % MOD; return ans; } }; mat state; mat pow_mod(ll k) { if (k == 1) return state; mat a = pow_mod(k / 2); mat ans = a * a; if (k % 2) ans = ans * state; return ans; } int main() { int cas; scanf("%d", &cas); while (cas--) { scanf("%d%I64d", &n, &k); for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) scanf("%d", &state.s[i][j]); mat c = pow_mod(k); int ans = 0; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (i == j) ans += c.s[i][j]; printf("%d\n", ans % MOD); } return 0; }
题目链接
HDU1575-Tr A(矩阵快速幂)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。