快速幂和矩阵快速幂

快速幂的思想就是减少相乘的次数，将原本n-1次的相乘减小到（lg（n））的复杂度；

a^b=(a^2)^(b/2)

这个式子由于/是整除，所以得分奇偶的不同情况，偶数时仍然成立，奇数时需要再乘上一个a；

所以快速幂就是将原本的以a为基本单位的连乘改成以a*a为单位的连乘；

代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #define ll long long 
 5 using namespace std;
 6 ll quickpow(ll a,ll n,ll mod)//计算的大多是要对mod；
 7 {
 8     int ans=1;
 9     while(n)
10     {
11         if(n&1)
12             ans=ans*a%mod;
13         a=a*a%mod;
14         b/=2;
15     }
16     return ans;
17 }
18 int main()
19 {
20     int a,b,mod;
21     cin>>a>>b>>mod;
22     int ans=quickpow(a,b,mod);
23     cout<<ans<<endl;
24     return 0;
25 }

矩阵的快速幂是在这个的思想的基础上的，对矩阵进行更新；

题目背景

矩阵快速幂

题目描述

给定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 算法：矩阵快速幂

代码：

 1 #include<bits/stdc++.h>
 2 #define il inline
 3 #define ll long long
 4 using namespace std;
 5 const int mod=1e9+7;
 6 ll n,k;
 7 struct mat{ll a[102][102],r,c;};
 8 il mat mul(mat x,mat y)
 9 {
10     mat p;
11     memset(&p,0,sizeof(p));
12     p.r=x.r,p.c=y.c;
13     for(int i=0;i<x.r;i++)
14         for(int j=0;j<y.c;j++)
15             for(int k=0;k<x.c;k++)
16     p.a[i][j]=(p.a[i][j]+x.a[i][k]*y.a[k][j])%mod;
17     return p;
18 }
19 il ll gi()
20 {
21     ll a=0;char x=getchar();bool f=0;
22     while((x<'0'||x>'9')&&x!='-')x=getchar();
23     if(x=='-')x=getchar(),f=1;
24     while(x>='0'&&x<='9')a=a*10+x-48,x=getchar();
25     return f?-a:a;
26 }
27 int main()
28 {
29     ios::sync_with_stdio(0);
30     n=gi(),k=gi();
31     mat p,ans;
32     p.r=p.c=ans.r=ans.c=n;
33     for(int i=0;i<n;i++)
34         for(int j=0;j<n;j++)p.a[i][j]=gi(),ans.a[i][j]=p.a[i][j];
35     k--;
36     while(k)
37     {
38         if(k&1)ans=mul(ans,p);
39         k>>=1;
40         p=mul(p,p);
41     }
42     for(int i=0;i<n;i++){
43         for(int j=0;j<n;j++)cout<<ans.a[i][j]<<' ';
44         cout<<endl;
45     }
46     return 0;
47 }

不懂的可以点这里