矩阵快速幂是一个快速幂的延伸, 但实际上区别不大, 主要思想是一样的.
题干:
题目背景
题目描述
给定 n*n 的矩阵 A, 求 A^k
输入输出格式
输入格式:
第一行, n,k
第 2 至 n+1 行, 每行 n 个数, 第 i+1 行第 j 个数表示矩阵第 i 行第 j 列的元素
输出格式:
输出 A^k
共 n 行, 每行 n 个数, 第 i 行第 j 个数表示矩阵第 i 行第 j 列的元素, 每个元素模 10^9+7
输入输出样例
输入样例 #1: 复制
2 1
1 1
1 1
输出样例 #1: 复制
1 1
1 1
说明
n<=100, k<=10^12, | 矩阵元素 |<=1000 算法: 矩阵快速幂
代码:
- #include<iostream>
- #include<cstdio>
- #include<cmath>
- #include<ctime>
- #include<queue>
- #include<algorithm>
- #include<cstring>
- using namespace std;
- #define duke(i,a,n) for(int i = a;i <= n;i++)
- #define lv(i,a,n) for(int i = a;i>= n;i--)
- #define clean(a) memset(a,0,sizeof(a))
- #define mp make_pair
- #define pr pair<int,int>
- const int INF = 1e9 + 7;
- typedef long long ll;
- typedef double db;
- #define mod 1000000007
- template <class T>
- void read(T &x)
- {
- char c;
- bool op = 0;
- while(c = getchar(), c <'0' || c> '9')
- if(c == '-') op = 1;
- x = c - '0';
- while(c = getchar(), c>= '0' && c <= '9')
- x = x * 10 + c - '0';
- if(op) x = -x;
- }
- template <class T>
- void write(T x)
- {
- if(x <0) putchar('-'), x = -x;
- if(x>= 10) write(x / 10);
- putchar('0' + x % 10);
- }
- ll n,k;
- struct node
- {
- ll m[120][120];
- };
- node mi()
- {
- node k;
- duke(i,1,n)
- {
- k.m[i][i] = 1;
- }
- return k;
- }
- node mul(node x,node y)
- {
- node k;
- duke(i,1,n)
- duke(j,1,n)
- k.m[i][j] = 0;
- duke(i,1,n)
- {
- duke(j,1,n)
- {
- duke(z,1,n)
- {
- k.m[i][j] = (k.m[i][j] + x.m[i][z] * y.m[z][j] % mod) % mod;
- }
- }
- }
- return k;
- }
- node ksm(node a,ll b)
- {
- node tmp = mi();
- while(b)
- {
- if(b & 1)
- tmp = mul(tmp,a);
- a = mul(a,a);
- b>>= 1;
- }
- return tmp;
- }
- void output(node x)
- {
- duke(i,1,n)
- {
- duke(j,1,n)
- {
- printf("%lld",x.m[i][j]);
- }
- puts("");
- }
- return;
- }
- int main()
- {
- read(n);read(k);
- node a;
- duke(i,1,n)
- {
- duke(j,1,n)
- {
- read(a.m[i][j]);
- }
- }
- node res = ksm(a,k);
- output(res);
- return 0;
- }
- /*
- 2 1
- 1 1
- 1 1
- */
[模板] 矩阵快速幂
来源: http://www.bubuko.com/infodetail-2776149.html