（數論專題）【 快速幂 模闆詳解 】
快速幂
%mod怎麼快速算出來？
舉個例子：
怎麼快速算出來呢？ 162的二進制為10100010，是以162 =
+
+
= 128+32+2， 這樣
=
*
*
這樣就可以得到下面的代碼了； a維護的是
， 上面1,2,4,8,16,就是2的多少次方。。n&1==1的時候表示答案需要乘以這個ai
代碼：
ll qpow( ll a, ll n )
{
ll re = 1;
while ( n ) {
if ( n&1 ) {
re = (re*a)%mod;
}
n >>= 1;
a = (a*a)%mod;
}
return re;
}
乘法快速幂
a*n怎麼快速的算出來？
舉個例子： 12*162怎麼算？ 162的二進制為10100010， 對應
+
+
= 128+32+2 ， 12*162 = 12*128 + 12*32 + 12*2.
這樣類似上面的代碼，隻要把乘法改成加法就好了，剛開始的re為幺元e，加法幺元為0
代碼：
ll qmul( ll a, ll n )
{
ll re = 0;
while ( n ) {
if ( n&1 ) {
re = (re+a)%mod;
}
n >>= 1;
a = (a+a)%mod;
}
return re;
}
矩陣快速幂
我們隻要把
中的a改成矩陣A，乘法改成矩陣的乘法，就可以了， 為了友善我們矩陣快速幂就隻用來算n*n的矩陣乘法。
代碼：
#include <iostream>
#include <string.h>
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
const int maxn = 2;
struct node {
ll m[maxn][maxn];
void init() { // 初始化為機關矩陣
memset(m,0,sizeof(m));
for ( ll i=0; i<maxn; i++ ) m[i][i]=1;
}
};
node mul( node a, node b ) // 矩陣乘法， a*b
{
node ans;
ll i,j,k;
for ( i=0; i<maxn; i++ ) {
for ( j=0; j<maxn; j++ ) {
ans.m[i][j] = 0;
for ( k=0; k<maxn; k++ ) {
ans.m[i][j] += ( a.m[i][k]*b.m[k][j] )%mod; // 矩陣乘法的精髓
ans.m[i][j] %= mod;
}
}
}
return ans;
}
node t = { // 矩陣A， 求A的n次方
1,1,
1,0
};
node qpow( ll n )
{
node re, a=t;
re.init(); // 注意初始化
while ( n ) {
if ( n&1 ) {
re = mul(re,a);
}
n >>= 1;
a = mul(a,a);
}
return re;
}
int main()
{
cin >> k;
node ans = qpow(k);
return 0;
}
例題1：
Fibonacci POJ - 3070
題意：fabs[0] = 0, fabs[1] = 1, fabs[n] = fabs[n-1] + fabs[n-2]. 因為n很大，用for循環會T， 是以用矩陣快速幂來算。
左邊和右邊的2*1矩陣是一種套路，容易寫出來， 重點就是推出中間的數字方陣。
代碼：
#include <iostream>
#include <string.h>
using namespace std;
typedef long long ll;
const int mod = 10000;
const int maxn = 2;
struct node {
ll m[maxn][maxn];
void init() {
memset(m,0,sizeof(m));
for ( ll i=0; i<maxn; i++ ) m[i][i]=1;
}
};
node mul( node a, node b )
{
node ans;
ll i,j,k;
for ( i=0; i<maxn; i++ ) {
for ( j=0; j<maxn; j++ ) {
ans.m[i][j] = 0;
for ( k=0; k<maxn; k++ ) {
ans.m[i][j] += ( a.m[i][k]*b.m[k][j] )%mod;
ans.m[i][j] %= mod;
}
}
}
return ans;
}
node t = {
1,1,
1,0
};
node qpow( ll n )
{
node re, a=t;
re.init();
while ( n ) {
if ( n&1 ) {
re = mul(re,a);
}
n >>= 1;
a = mul(a,a);
}
return re;
}
int main()
{
ll k;
while (cin >> k) {
if ( k==-1 ) break ;
if ( k==0 ) {
cout << "0" << endl;
continue ;
}
node ans = qpow(k-1);
cout << ans.m[0][0] << endl;;
}
return 0;
}
例題2：
C - Recursive sequence HDU - 5950
題意：f(n) = 2*f(n-2) + f(n-1) +
, 給出f(1), f(2), 求f(n).
類似的左邊先寫出f(n)和f(n-1), 右邊寫出f(n-1)和f(n-2)， 但我們發現想要湊出f(n)來缺一個
，是以在右邊補一個
， 根據左右對稱左邊多了一個
, 現在又需要湊
， 左邊需要....
注：此題有個天坑，取模的值居然爆int了。 應該是const long long mod = 2147493647 。
做出矩陣關系如下：
代碼：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 2147493647;
struct node {
ll m[7][7];
void init() {
memset(m,0,sizeof(m));
for ( int i=0; i<7; i++ ) m[i][i] = 1;
}
};
node A = {
1,2,1,0,0,0,0,
1,0,0,0,0,0,0,
0,0,1,4,6,4,1,
0,0,0,1,3,3,1,
0,0,0,0,1,2,1,
0,0,0,0,0,1,1,
0,0,0,0,0,0,1
};
node mul( node a, node b )
{
node ans;
ll i,j,k;
for ( i=0; i<7; i++ ) {
for ( j=0; j<7; j++ ) {
ans.m[i][j] = 0;
for ( k=0; k<7; k++ ) {
ans.m[i][j] += ((a.m[i][k])*(b.m[k][j]))%mod;
ans.m[i][j] %= mod;
}
}
}
return ans;
}
node qpow( int k )
{
node re,a=A;
re.init();
while ( k ) {
if ( k&1 ) {
re = mul(re,a);
}
k >>= 1;
a = mul(a,a);
}
return re;
}
int main()
{
int listt;
cin >> listt;
while ( listt-- ) {
ll n,a,b;
cin >> n >> a >> b;
if ( n==1 ) cout << a << endl;
else if ( n==2 ) cout << b << endl;
else {
node ans = qpow(n-2);
ll sum = 0;
sum += ans.m[0][0]*b;
sum += ans.m[0][1]*a;
sum += ans.m[0][2]*81;
sum += ans.m[0][3]*27;
sum += ans.m[0][4]*9;
sum += ans.m[0][5]*3;
sum += ans.m[0][6]*1;
sum %= mod;
cout << sum << endl;
}
}
return 0;
}