首页 > 代码库 > Hdu1575Tr A矩阵
Hdu1575Tr A矩阵
矩阵快速幂,就是快速幂的乘法变成矩阵乘法,其余的都一样。
#include <cstdio>#include <algorithm>#include <iostream>#include <string.h>using namespace std;const int mod = 9973;const int maxn = 12;struct Matrix{ int m[maxn][maxn];};int n;Matrix Mul(Matrix a, Matrix b){ Matrix ans; for (int i = 0; i < n; i++){ for (int j = 0; j < n; j++){ ans.m[i][j] = 0; for (int k = 0; k < n; k++){ ans.m[i][j] += (a.m[i][k] * b.m[k][j]); ans.m[i][j] %= mod; } } } return ans;}Matrix fast(Matrix a, int sum){ Matrix ans; for (int i = 0; i < n;i++) for (int j = 0; j < n; j++) ans.m[i][j] = (i == j); while (sum){ if (sum & 1) ans = Mul(ans, a); a = Mul(a, a); sum /= 2; } return ans;}int main(){ int t,k; cin >> t; Matrix a; while (t--){ cin >> n >> k; for (int i = 0; i < n;i++) for (int j = 0; j < n; j++) cin >> a.m[i][j]; Matrix gao = fast(a, k); int ans = 0; for (int i = 0; i < n; i++) ans += gao.m[i][i], ans %= mod; printf("%d\n", ans); } return 0;}
Hdu1575Tr A矩阵
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。