快速幂与矩阵快速幂
快速幂
求a^b mod p ，a的b次方模上p
求幂这种算法一般在初学程序设计语言的时候应该都有联系过，只要写一个简单的循环就能够搞定。
/**
* 普通的求幂函数
* @param base 底数
* @param power 指数
* @param p 模
* @return a^b mod p
*/
#define ll long long
ll normalPower(ll base,ll power，ll p){
ll result=1;
for(int i=1;i<=power;i++){
result=result*base;
}
return result%p;
}
但是这样求解是存在问题的
如果题目让你求2的100次方，貌似我们程序设计语言中最大的long lnog类型也无法承载这么大的数值，所以题目才不会要求你输出结果，因为结果可能会非常的大，大到没有任何类型可以承载。
指数的概念：
指数：在乘方a中，其中的a叫做底数，n叫做指数，结果叫幂。
f(x)=a^x ， 随着x单位长度的递增，f(x)会呈“爆炸性”增长。
一张纸对折一次，厚度变成原来的2倍。再对折第二次，变为原来的2的2次方倍即4倍。以此类推，假设纸的厚度为0.1mm，则对折24次以后，长度超过1千米；对折39次达55000千米，超过地球赤道长度；对折42次达44万千米，超过地球至月球的距离；对折51次达22亿千米，超过地球至太阳的距离；对折82次为51113光年，超过银河系半径的长度。
“取模”运算的运算法则：
(a + b) % p = (a % p + b % p) % p
(a - b) % p = (a % p - b % p ) % p
(a * b) % p = (a % p * b % p) % p
(a * b) % p = (a % p * b % p) % p ，我们仔细研究一下这个运算法则，会发现多个因子连续的乘积取模的结果等于每个因子取模后的乘积再取模的结果。也就是说，我们如果要求：
(abc)%d=(a%d *b%d *c%d )%d;
因此，我们可以借助这个法则，只需要在循环乘积的每一步都提前进行“取模”运算，而不是等到最后直接对结果“取模”，也能达到同样的效果。
/**
* 普通的求幂函数
* @param base 底数
* @param power 指数
* @return 求幂结果的最后3位数表示的整数
*/
ll normalPower(ll base,ll power，ll p){
long long result=1;
for(int i=1;i<=power;i++){
result=result*base;
result=result%p;
}
return result%p;
}
再次思考
虽然这个求幂的方法很有用，但是我们来考虑一下这个算法的时间复杂度，假设我们求2的100次方，那么将会执行100次循环。如果我们分析一下这个算法，就会发现这个算法的时间复杂度为O(N),其中N为指数。求一下小的结果还好，那如果我们要求2的1000000000次方呢？这个程序可能会运行很久很久
//ac 代码
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<b;i++)
#define loop(i,a,b) for(int i=(a);i<=b;i++)
#define pb push_back
#define ll long long
#define el '\n'
#define gc getchar()
#define debug(x) cerr<<#x<<":"<<x<<endl
const int N=2e4+10;
int father[N];
ll fastPower(ll a,ll b,ll p){
ll result=1;
while(b){
if(b&1) result=result*a%p;
b>>=1;
a=a*a%p;
}
return result;
}
int main()
{
ll a,b,p;
cin>>a>>b>>p;
cout<<a<<"^"<<b<<" mod "<<p<<"="<<fastPower(a,b,p)<<el;
return 0;
}
矩阵快速幂
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<b;i++)
#define loop(i,a,b) for(int i=(a);i<=b;i++)
#define pb push_back
#define el '\n'
#define gc getchar()
#define cl putchar('\n')
long long n, k;
const int mod = 1e9 + 7;
struct An {
long long Data[103][103];
An() {
memset(Data, 0, sizeof Data);
rep(i, 0, 103) Data[i][i] = 1;
}
};
An muli(An a, An b) {
An result;
rep(i, 0, n) {
rep(j, 0, n) {
result.Data[i][j] = 0;
rep(k,0,n)
result.Data[i][j]=(result.Data[i][j]+a.Data[i][k] * b.Data[k][j]) % mod;
}
}
return result;
}
void Print(An a) {
rep(i, 0, n) {
rep(j, 0, n)
{
if (j == 0)cout << a.Data[i][j];
else cout << " " << a.Data[i][j];
}
cout << el;
}
}
An fastPower(An a,long long k) {
An result;
while (k) {
if (k % 2 == 1) result = muli(result, a);
a = muli(a, a);
//Print(a);
k/= 2;
}
return result;
}
int main()
{
An a;
cin >> n >> k;
rep(i, 0, n)
rep(j, 0, n) {
cin >> a.Data[i][j];
}
a = fastPower(a, k);
Print(a);
return 0;
}
求解斐波那契数列
输入输出样例
输入 #1复制
5
输出 #1复制
5
输入 #2复制
10
输出 #2复制
55
求解思路
参考代码
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<b;i++)
#define loop(i,a,b) for(int i=(a);i<=b;i++)
#define pb push_back
#define ll long long
#define el '\n'
#define gc getchar()
#define debug(x) cerr<<#x<<":"<<x<<endl
const int mod = 1e9 + 7;
#define ll long long
struct mat {
long long Data[2][2];
mat() {
Data[0][0] = Data[0][1] = Data[1][0] = 1;
Data[1][1] = 0;
}
};
mat multi(mat a, mat b) {
mat res;
rep(i, 0, 2) {
rep(j, 0, 2) {
res.Data[i][j] = 0;
rep(k, 0, 2)
res.Data[i][j] += (a.Data[i][k] * b.Data[k][j]) % mod;
res.Data[i][j] %= mod;
}
}
return res;
}
long long fast_power(long long n) {
mat a;
mat res;
memset(res.Data, 0, sizeof res.Data);
rep(i, 0, 2) res.Data[i][i] = 1;
while (n) {
if (n % 2 == 1) res = multi(res, a);
n /= 2;
a = multi(a, a);
}
return res.Data[0][0]%mod;
}
int main()
{
ll n;
cin >> n;
cout << fast_power(n - 1)%mod;
return 0;
}
矩阵加速
https://www.luogu.com.cn/problem/P1939
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<b;i++)
#define loop(i,a,b) for(int i=(a);i<=b;i++)
#define pb push_back
#define ll long long
#define el '\n'
#define gc getchar()
#define debug(x) cerr<<#x<<":"<<x<<endl
#define cl putchar('\n')
const int mod = 1e9 + 7;
#define ll long long
struct mat {
long long da[3][3]= { {1,0,1},{1,0,0},{0,1,0} };
};
mat multi(mat a, mat b) {
mat res;
rep(i, 0, 3) {
rep(j, 0, 3) {
res.da[i][j] = 0;
rep(k, 0, 3) {
res.da[i][j] = (res.da[i][j] + a.da[i][k] * b.da[k][j]) % mod;
}
}
}
return res;
}
ll fast_power(ll n) {
mat res;
mat a;
memset(res.da, 0, sizeof res.da);
res.da[0][0] = res.da[1][1] = res.da[2][2] = 1;
while (n) {
if (n % 2 == 1) res = multi(res, a);
n /= 2;
a = multi(a, a);
}
/*
* rep(i, 0, 3) {
rep(j, 0, 3)
cout << res.da[i][j];
cl;
}
*/
return (res.da[0][0] + res.da[0][2]+res.da[0][1])%mod;
}
int main()
{
ll time;
cin >> time;
while (time--) {
ll n;
cin >> n;
if (n <= 3) cout << 1 << el;
else
cout << fast_power(n - 3) << el;
}
}
广义斐波那契数列
https://www.luogu.com.cn/problem/P1349
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<b;i++)
#define loop(i,a,b) for(int i=(a);i<=b;i++)
#define pb push_back
#define ll long long
#define el '\n'
#define gc getchar()
#define debug(x) cerr<<#x<<":"<<x<<endl
#define cl putchar('\n')
const int mod = 1e9 + 7;
#define ll long long
ll p, q;
ll a1, a2, n, m;
struct mat {
long long da[2][2];
mat() {
da[0][0] = p, da[0][1] = q;
da[1][0] = 1;
da[1][1] = 0;
}
};
mat multi(mat a, mat b) {
mat res;
rep(i, 0, 2) {
rep(j, 0, 2) {
res.da[i][j] = 0;
rep(k, 0, 2) res.da[i][j] = (res.da[i][j] + a.da[i][k] * b.da[k][j]) % m;
}
}
return res;
}
ll fi(ll n) {
mat res;
mat a;
res.da[0][0] = res.da[1][1] = 1;
res.da[0][1] = res.da[1][0]=0;
while (n) {
if (n % 2 == 1) res = multi(res, a);
a = multi(a, a);
n /= 2;
}
return (res.da[0][0] * a2 + res.da[0][1] * a1)%m;
}
int main()
{
cin >> p >> q >> a1 >> a2 >> n >> m;
cout << fi(n - 2);
}
[NOI2012] 随机数生成器
https://www.luogu.com.cn/problem/P2044
#include<iostream>
#include<algorithm>
#define rep(i,a,b) for(int i=(a);i<b;i++)
#define el '\n'
using namespace std;
#define ll long long
struct mat {
ll a[2][2];
mat() {
a[0][0] = 1;
a[0][1] = 0;
a[1][0] = 0;
a[1][1] = 1;
}
};
ll g, m, a, c, X0, n;
ll slow_muti(ll a, ll b) {
ll result = 0;
while (b) {
if (b % 2 == 1) (result += a)%=m;
(a += a)%=m ;
b /= 2;
}
return result%m;
}
mat muli(mat a, mat b) {
mat result;
result.a[0][0] = 0;
result.a[1][1] = 0;
rep(i, 0, 2) {
rep(j, 0, 2) {
rep(k,0,2)
//(result.a[i][j] += a.a[i][k]* b.a[k][j]) %= m;
(result.a[i][j] += slow_muti(a.a[i][k], b.a[k][j]))%=m;
}
}
return result ;
}
ll fast_power(mat a, long long b) {
mat result;
while (b) {
if (b % 2 == 1) result = muli(result, a);
a = muli(a, a);
b /= 2;
}
/*rep(i, 0, 2) {
rep(j, 0, 2) cout << result.a[i][j] << " ";
cout << el;
}*/
return (slow_muti(result.a[0][0], X0) %m + slow_muti(result.a[0][1] , c) )%m%g;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> m >> a >> c >> X0 >> n >> g;
mat ans;
ans.a[0][0] = a%m;
ans.a[0][1] = 1;
ans.a[1][0] = 0;
ans.a[1][1] = 1;
if (n == 0) cout << 0 << el;
else
cout << fast_power(ans, n)<<el;
}