幂运算
众所周知，在NOIP系列竞赛中，会考到许多优化，而这些许多优化是由一个个简单的优化组件而来的，使整个程序的优化尽可能地达到最大，用最少的时间和空间来实现正确代码，而幂运算作为其中的一个基本我今天就来总结一下，如有不足，以后也会加勘误and Update。
幂
普遍数学上幂的意义是一个数做自乘的运算，如a的b次方意思是b个a相乘，使表示上更加简便
普通幂
C++中普通幂的代码很容易实现，这是实现代码(基本实现代码)
1
2
3
4
5
6
7
8
9
10
11
| #include <iostream>
using namespace std;
int main()
{
int a,b;
cin>>a>>b;
for(int i=2;i<=b;i++)
a*=a;
cout<<a<<endl;
return 0;
}
|
快速幂
在普通幂中发现算很大的数的时候回非常地慢，我们就要想怎么优化，怎么优化呢，我们引入一组基本公式
ab=a2b∗a2b(b为偶数)
ab=a2b∗a2b∗a(b为奇数)
我们发现这样可以利用递归解决子问题来快速地算出a的b次方，加速了运算
代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| #include <iostream>
using namespace std;
int a,b;
int quick_pow(int a,int b)
{
if(b==0)
return 1;
int t=quick_pow(a,b/2);
if(b%2==1)
return t*t*a;
else
return t*t;
}
int main()
{
cin>>a>>b;
cout<<quick_pow(a,b)<<endl;
return 0;
}
|
或者代码也可以这样
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| #include <iostream>
using namespace std;
int power(int a,int b,int p)
{
int ans=1%p;
while(b)
{
if(b&1)
ans=(long long)ans*a%p;
a=(long long)a*a%p;
b>>=1;
}
return ans;
}
int main()
{
int a,b,p;
cin>>a>>b>>p;
cout<<power(a,b,p)<<endl;
return 0;
}
|
特殊情况下算2的n次幂可以直接
1<<n
矩阵快速幂
矩阵快速幂是一个对于矩阵的快速幂
你还不知道什么是矩阵吗？（快速查看：矩阵）
矩阵快速幂是对于矩阵乘法的自己多次相乘的快速运算
和普通快速幂差不多，只是把‘*’换成了一个mul函数
代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| mat mul(mat x,mat y)
{
mat c;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
c.m[i][j]=0;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
for(int k=1;k<=n;k++)
c.m[i][j]=(c.m[i][j]%mod+(x.m[i][k]*y.m[k][j])%mod)%mod;
}
}
return c;
}
|
因为要返回一个数组，所以为了方便，我们新建了一个结构体，也就是mat
1
2
3
4
| struct mat
{
long long m[1005][1005];
};
|
这样我们在写一个类似于普通快速幂的函数就成功解决问题了
类普通快速幂函数
1
2
3
4
5
6
7
8
9
10
11
12
| mat pow(mat a,long long b)
{
mat ans=e;
while(b)
{
if(b&1)
ans=mul(ans,a);
a=mul(a,a);
b>>=1;
}
return ans;
}
|
所以我们就做出来了，但是为了使整个矩阵能保持原样，这个说不清，自己去看单位矩阵，然后这就是一个巧妙的地方
1
2
| for(int i=1;i<=n;i++)
e.m[i][i]=1;
|
最后，矩阵快速幂的一道模板题发给大家
lgP3390【模板】矩阵快速幂
提交 25.45k
通过 8.58k
时间限制 1.00s
内存限制 125.00MB
题目背景
矩阵快速幂
题目描述
给定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
输出 #1
说明/提示
n<=100, k<=10^12, |矩阵元素|<=1000 算法：矩阵快速幂
AC代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
| #include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn=1005;
const int mod=1000000007;
struct mat
{
long long m[maxn][maxn];
};
mat a,e;
long long n,p;
mat mul(mat x,mat y)
{
mat c;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
c.m[i][j]=0;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
for(int k=1;k<=n;k++)
c.m[i][j]=(c.m[i][j]%mod+(x.m[i][k]*y.m[k][j])%mod)%mod;
}
}
return c;
}
mat pow(mat a,long long b)
{
mat ans=e;
while(b)
{
if(b&1)
ans=mul(ans,a);
a=mul(a,a);
b>>=1;
}
return ans;
}
int main()
{
cin>>n>>p;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
cin>>a.m[i][j];
}
for(int i=1;i<=n;i++)
e.m[i][i]=1;a
mat s=pow(a,p);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
cout<<s.m[i][j]<<" ";
cout<<endl;
}
return 0;
}
|
PS:在自己电脑上可能输出不了，但是在洛谷IDE上能正常运行啊
这就奇怪了，请问一下各位为什么
下集预告：单源最短路径的优化或矩阵的简单介绍
