首页 > 代码库 > 快速幂应用
快速幂应用
矩阵快速幂自乘
typedef vector< int > vec;
typedef vector< vector< int > > mat;
mat multi( const mat& A, const mat& B ){
mat C( A.size(), vec ( B[0].size() ) );
for( int i = 0; i < A.size(); ++i ){
for( int k = 0; k < B.size(); ++k ){
for( int j = 0; j < B[0].size(); ++j ){
C[i][j] = ( C[i][j] + A[i][k] * B[k][j] ) % MOD;
}
}
}
return C;
}
mat quick_pow( mat& A, LL n ){
int row = A.size();
int col = A[0].size();
mat B( row, vec( col ) );
for( int i = 0; i < row; ++i ){
B[i][i] = 1;
}
while( n > 0 ){
if( n & 1 )
B = multi( B, A );
A = multi( A, A );
n >>= 1;
}
return B;
}Google Code Jam -- Number( 2008 Round C )
求 ( 3 + 5 ^ 0.5 ) ^ N ( 1 <= N <= 10 ^ 9 ) 整数部分的最后三位，不足三位数的话首部填零。
( 3 + 5 ^ 0.5 ) ^ N 都可以变形为 ( A + B * ( 5 ^ 0.5 ) ) 的结构
( 3 + 5 ^ 0.5 ) ^ ( N + 1 ) = ( 3 + 5 ^ 0.5 ) * ( 3 + 5 ^ 0.5 ) ^ N
= ( 3 + 5 ^ 0.5 ) * ( A + B * ( 5 ^ 0.5 ) )
= ( A‘ + B‘ * ( 5 ^ 0.5 ) )
A‘ = 3 * A + 5 * B
B‘ = A + 3 * B
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
#define MOD 1000
#define LL long long
typedef vector< int > vec;
typedef vector< vector< int > > mat;
mat multi( const mat& A, const mat& B ){
mat C( A.size(), vec ( B[0].size() ) );
for( int i = 0; i < A.size(); ++i ){
for( int k = 0; k < B.size(); ++k ){
for( int j = 0; j < B[0].size(); ++j ){
C[i][j] = ( C[i][j] + A[i][k] * B[k][j] ) % MOD;
}
}
}
return C;
}
mat quick_pow( mat& A, LL n ){
int row = A.size();
int col = A[0].size();
mat B( row, vec( col ) );
for( int i = 0; i < row; ++i ){
B[i][i] = 1;
}
while( n > 0 ){
if( n & 1 )
B = multi( B, A );
A = multi( A, A );
n >>= 1;
}
return B;
}
int main(){
LL n;
mat A( 2, vec( 2, 0 ) );
A[0][0] = 3; A[0][1] = 5;
A[1][0] = 1; A[1][1] = 3;
cin >> n;
A = quick_pow( A, n );
printf( "%03d\n", ( A[0][0] * 2 + MOD - 1 ) % MOD );
return 0;
}
POJ 3070 斐波那契
求解第 N( 1 <= N <= 10 ^ 9 ) 个斐波那契数
| F( n + 2 ) | | 1 1 | | F( n + 1 ) |
| | = | | * | |
| F( n + 1 ) | | 1 0 | | F( n ) |
| F( n + 1 ) | | F( 1 ) |
| | = A ^ n * | |
| F( n ) | | F( 0 ) |
#include <iostream>
#include <vector>
using namespace std;
#define MOD 10007
#define LL long long
typedef vector< int > vec;
typedef vector< vector< int > > mat;
mat multi( const mat& A, const mat& B ){
mat C( A.size(), vec ( B[0].size() ) );
for( int i = 0; i < A.size(); ++i ){
for( int k = 0; k < B.size(); ++k ){
for( int j = 0; j < B[0].size(); ++j ){
C[i][j] = ( C[i][j] + A[i][k] * B[k][j] ) % MOD;
}
}
}
return C;
}
mat quick_pow( mat& A, LL n ){
int row = A.size();
int col = A[0].size();
mat B( row, vec( col ) );
for( int i = 0; i < row; ++i ){
B[i][i] = 1;
}
while( n > 0 ){
if( n & 1 )
B = multi( B, A );
A = multi( A, A );
n >>= 1;
}
return B;
}
int main(){
int test;
cin >> test;
while( test-- ){
LL n;
mat A( 3, vec ( 3 ) );
A[0][0] = 2; A[0][1] = 1; A[0][2] = 0;
A[1][0] = 2; A[1][1] = 2; A[1][2] = 2;
A[2][0] = 0; A[2][1] = 1; A[2][2] = 2;
cin >> n;
A = quick_pow( A, n );
cout << A[0][0] << endl;
}
return 0;
}POJ 3734 Blocks
一行 N 个方块，每块只能用用 A, B, C, D 四种之一颜色涂满，求含有偶数个颜色 A 和 偶数个颜色 B 的方块的涂色方案的个数。
递推：
涂到第 i 块的时后，A, B 都是偶数的方案个数为 X，一奇一偶方案个数为 Y，全为奇数方案个数为 Z
那么低 i + 1 的可能性：
X‘ = 2 * X + Y
Y‘ = 2 * X + 2 * Y + 2 * Z
Z‘ = Y + 2 * Z
#include <iostream>
#include <vector>
using namespace std;
#define MOD 10007
#define LL long long
typedef vector< int > vec;
typedef vector< vector< int > > mat;
mat multi( const mat& A, const mat& B ){
mat C( A.size(), vec ( B[0].size() ) );
for( int i = 0; i < A.size(); ++i ){
for( int k = 0; k < B.size(); ++k ){
for( int j = 0; j < B[0].size(); ++j ){
C[i][j] = ( C[i][j] + A[i][k] * B[k][j] ) % MOD;
}
}
}
return C;
}
mat quick_pow( mat& A, LL n ){
int row = A.size();
int col = A[0].size();
mat B( row, vec( col ) );
for( int i = 0; i < row; ++i ){
B[i][i] = 1;
}
while( n > 0 ){
if( n & 1 )
B = multi( B, A );
A = multi( A, A );
n >>= 1;
}
return B;
}
int main(){
int test;
cin >> test;
while( test-- ){
LL n;
mat A( 3, vec ( 3 ) );
A[0][0] = 2; A[0][1] = 1; A[0][2] = 0;
A[1][0] = 2; A[1][1] = 2; A[1][2] = 2;
A[2][0] = 0; A[2][1] = 1; A[2][2] = 2;
cin >> n;
A = quick_pow( A, n );
cout << A[0][0] << endl;
}
return 0;
}快速幂应用