首页 > 代码库 > 矩阵快速幂(入门) 学习笔记hdu1005, hdu1575， hdu1757
矩阵快速幂(入门) 学习笔记hdu1005, hdu1575， hdu1757
矩阵快速幂是基于普通的快速幂的一种扩展，如果不知道的快速幂的请参见http://www.cnblogs.com/Howe-Young/p/4097277.html。二进制这个东西太神奇了，好多优秀的算法都跟他有关系，这里所说的矩阵快速幂就是把原来普通快速幂的数换成了矩阵而已，只不过重载了一下运算符*就可以了，也就是矩阵的乘法， 当然也可以写成函数，标题中的这三个题都是关于矩阵快速幂的基础题。拿来练习练习熟悉矩阵快速幂，然后再做比较难点的，其实矩阵快速幂比较难的是构造矩阵。下面还是那题目直接说话：
hdu1575：
题目大意：求一个矩阵k此方之后主对角线上的元素之和对9973取模
这个题是矩阵快速幂的裸题，直接用就行了。下面是代码
1 #include<iostream> 2 #include <string.h> 3 #include <stdio.h> 4 #include <algorithm> 5 6 using namespace std; 7 const int N = 11; 8 const int mod = 9973; 9 struct Matrix{10 int a[N][N];11 };12 int n;13 Matrix operator * (Matrix t1, Matrix t2)//重载运算符 * 14 {15 Matrix c;16 memset(c.a, 0, sizeof(c.a));17 //矩阵乘法 18 for (int k = 0; k < n; k++)19 {20 for (int i = 0; i < n; i++)21 {22 if (t1.a[i][k] <= 0)23 continue;24 for (int j = 0; j < n; j++)25 {26 if (t2.a[k][j] <= 0)27 continue;28 c.a[i][j] = (c.a[i][j] + t1.a[i][k] * t2.a[k][j]) % mod;29 }30 }31 }32 return c;33 }34 //重载^运算符 35 Matrix operator ^ (Matrix t, int k)36 {37 Matrix c;38 memset(c.a, 0, sizeof(c.a));39 //初始化矩阵c为单位阵 40 for (int i = 0; i < n; i++)41 {42 c.a[i][i] = 1;43 }44 //这里用到快速幂 45 for (; k; k >>= 1)46 {47 if (k & 1)48 c = c * t;49 t = t * t;50 }51 return c;52 }53 int main()54 {55 int T, k;56 cin >> T;57 while (T--)58 {59 cin >> n >> k;60 Matrix t1, t2;61 for (int i = 0; i < n; i++)62 {63 for (int j = 0; j < n; j++)64 cin >> t1.a[i][j];65 }66 t2 = t1 ^ k;67 int res = 0;68 for (int i = 0; i < n; i++)69 res = (res + t2.a[i][i]) % mod;70 cout << res << endl;71 }72 73 return 0;74 }
hdu1005：
题目大意：
f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7.
给你A， B和n让你求f(n)是多少
这个题就需要稍微构造一下矩阵了
这样的话要求F(n)的话，只需要对求出来F(n-1)就行了，对应的F(n-1)要求出F(n-2)，所以题目给了F(1)和F(2)，所以乘以他前面的系数矩阵就为【F(3), F(2)】T,再接着成系数矩阵就为【F(4)，F(3)】T所以要求F(n)只需要对系数矩阵进行n-2次幂就行了，然后最后要求的结果就是矩阵的第一行第一列的结果，代码如下
1 #include<iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <algorithm> 5 6 using namespace std; 7 const int N = 2; 8 const int mod = 7; 9 struct Matrix10 {11 int mat[N][N];12 };13 //矩阵乘法(函数的形式) 14 Matrix Multi(Matrix a, Matrix b)15 {16 Matrix c;17 memset(c.mat, 0, sizeof(c.mat));18 for (int i = 0; i < N; i++)19 {20 for (int j = 0; j < N; j++)21 {22 for (int k = 0; k < N; k++)23 c.mat[i][j] = (c.mat[i][j] + a.mat[i][k] * b.mat[k][j]) % mod;24 }25 }26 return c;27 }28 //矩阵快速幂 （函数形式） 29 Matrix quickMatrixPower(Matrix a, int k)30 {31 Matrix t;32 memset(t.mat, 0, sizeof(t.mat));33 for (int i = 0; i < N; i++)34 t.mat[i][i] = 1;35 //快速幂 36 while (k)37 {38 if (k & 1)39 t = Multi(t, a);40 a = Multi(a, a);41 k >>= 1;42 }43 return t;44 }45 46 int main()47 {48 long long a, b, n;49 while (cin >> a >> b >> n && (a + b + n))50 {51 Matrix t;52 //初始化系数矩阵 53 t.mat[0][0] = a; 54 t.mat[0][1] = b;55 t.mat[1][0] = 1;56 t.mat[1][1] = 0;57 if (n >= 3)58 {59 t = quickMatrixPower(t, n - 2);60 printf("%d\n", (t.mat[0][0] + t.mat[0][1]) % mod);61 }62 else63 {64 printf("%lld\n", n);65 }66 }67 68 69 return 0;70 }
hdu1757
题目大意：
If x < 10 f(x) = x.
If x >= 10 f(x) = a0 * f(x-1) + a1 * f(x-2) + a2 * f(x-3) + …… + a9 * f(x-10);
And ai(0<=i<=9) can only be 0 or 1 .
Now, I will give a0 ~ a9 and two positive integers k and m ,and could you help Lele to caculate f(k)%m.
这个关键还是在于构造矩阵，因为给递推式了，所以矩阵还是比价好构造的，下图是构造的矩阵
推到过程类似于1005，不再赘述，代码如下：
1 #include<iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 6 using namespace std; 7 const int ori[1][10] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0}; 8 struct Matrix 9 {10 int str[10][10];11 };12 int m;13 //矩阵乘法 14 Matrix operator * (Matrix a, Matrix b)15 {16 Matrix c;17 memset(c.str, 0, sizeof(c.str));18 for (int i = 0; i < 10; i++)19 {20 for (int j = 0; j < 10; j++)21 {22 for (int k = 0; k < 10; k++)23 c.str[i][j] = (c.str[i][j] + a.str[i][k] * b.str[k][j]) % m;24 }25 }26 return c;27 }28 //矩阵快速幂 29 Matrix power (Matrix a, int k)30 {31 Matrix c;32 memset(c.str, 0, sizeof(c.str));33 for (int i = 0; i < 10; i++)34 c.str[i][i] = 1;35 while (k)36 {37 if (k & 1)38 c = c * a;39 a = a * a;40 k >>= 1;41 }42 return c;43 }44 //最后一步的矩阵乘法 45 int Multi(Matrix a)46 {47 Matrix c;48 memset(c.str, 0, sizeof(c.str));49 for (int i = 0; i < 1; i++)50 {51 for (int j = 0; j < 10; j++)52 {53 for (int k = 0; k < 10; k++)54 {55 c.str[i][j] = (c.str[i][j] + ori[i][k] * a.str[k][j]) % m;56 }57 }58 }59 return c.str[0][0] % m;60 }61 int main()62 {63 int k;64 while (cin >> k >> m)65 {66 Matrix t;67 memset(t.str, 0, sizeof(t.str));68 for (int i = 0; i < 10; i++)69 {70 cin >> t.str[i][0];71 for (int j = 0; j < 10; j++)72 if (i + 1 == j)73 t.str[i][j] = 1;74 }75 if (k >= 10)76 {77 t = power(t, k - 9);78 printf("%d\n", Multi(t));79 }80 else81 {82 printf("%d\n", k);83 }84 }85 86 return 0;87 }
矩阵快速幂(入门) 学习笔记hdu1005, hdu1575， hdu1757
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。