快速幂：复杂度为logn,比普通的n快了很多了.
原理 :
以求a的b次方来介绍：
首先把b转换成二进制数
该二进制数第i位的权为 2^i - 1 .
比如 : 11的二进制是1011
11 = 2³×1 + 2²×0 + 2¹×1 + 2º×1
所以假设我们要求a^b，那么其实b是可以拆成二进制的，该二进制数第i位的权为2^(i-1)，例如当b==11时
a^11=a^(2^0+2^1+2^3)
实现代码如下:(位运算，简单，简洁)
long long pow(int a,int b) //位运算
{
long long r=1,base=a;
while(b)
{
if(b&1) r*=base; //r才是最终我们要的结果.
base *= base ; //一个中间转移量.b每右移一次,base就多一个平方.
b >>= 1 ;
}
return r;
}
矩阵快速幂:
思想和快速幂差不多,只是这里是矩阵 , 而那个是数的差别.
所以原理和思想就不多说了 , 然后直接上代码
while(b)
{
if(b&1) res *= A; //res是结果矩阵.
A *= A; //和快速幂一样,每一次都是乘一个平方,因为最多也是差2的几次方的问题.
b >>= 1 ;
}
难点在于如何构造A矩阵,只要构造出来了就简单了.
给一道好题:点这(自己通过看下面那篇博客,自己推推,尽量不要搜题解)
不知道怎么建矩阵的请看这里,这个讲的超级好点这里, 点这里, 看见了吗, 点这里啊
思路就是很简单:就是矩阵快速幂,主要是建好矩阵.
提供一个骚气的写法,就可以不用每一次写矩阵形式,就是重载 * 号运算符. 代码如下:
#define ll long long
#define db double
#define CLR(x) memset(x,0,sizeof(x))
const int ssize=10;
struct Ma{
db a[30][30];
void cc(){
CLR(a);
}
Ma operator * (const Ma &b) const { //重载 * 号运算符.
Ma tmp;
tmp.cc();
for(int i=0;i<ssize;i++){
for(int j=0;j<ssize;j++){
for(int k=0;k<ssize;k++){
if(b.a[k][j] == 0 || a[i][k] == 0) continue; //以后都把这个优化加上, 在有些卡数的题中会遇到.(如某个校赛F题)
tmp.a[i][j] += (a[i][k] * b.a[k][j]);
//tmp.a[i][j] %= mod;
}
}
}
return tmp;
}
}res,x; //有许多写法,这只是其中一种,我认为好理解点的!
(怎么推要求那个矩阵的几次方,就是用等比数列,an = a(n-1) * q ，然后看题目给的那一项从而推出是q的几次方.)
好题的AC代码:
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iostream>
#define ll long long
using namespace std;
const ll mod = 2147493647;
struct Ma
{
ll a[10][10];
void cc()
{
memset(a,0,sizeof(a));
}
Ma operator * (const Ma & b) const {
Ma tmp;
tmp.cc();
for(int i=0;i<7;i++){
for(int j=0;j<7;j++){
for(int k=0;k<7;k++){
tmp.a[i][j] += (a[i][k] * b.a[k][j]);
tmp.a[i][j] %= mod;
}
}
}
return tmp;
}
}res,x;
void init()
{
res.cc();
for(int i=0;i<7;i++) //初始化为单位矩阵.
res.a[i][i] = 1 ;
x.cc(); // 初始化所推的那个矩阵.
x.a[0][0] = x.a[0][1] = 1;
x.a[1][0] = 2;
x.a[2][0] = x.a[2][2] = 1;
x.a[3][2] = 4 , x.a[3][3]=1;
x.a[4][2] = 6 , x.a[4][3] = 3 ,x.a[4][4] = 1 ;
x.a[5][2] = 4 , x.a[5][3] = 3 , x.a[5][4] = 2 , x.a[5][5] = 1 ;
x.a[6][2] = x.a[6][3] = x.a[6][4] = x.a[6][5] = x.a[6][6] = 1;
}
void qpow(ll n)
{
while(n)
{
if(n&1) res = res * x;
x = x*x ;
n >>= 1;
}
}
int main()
{
int t;
cin >> t;
while(t--){
ll N,m,n;
init();
cin >> N >> m >> n;
if(N < 3){
if(N == 1)
cout << m << endl;
else
cout << n << endl;
continue;
}
ll s[10] = {n,m,81,27,9,3,1}; //相当于第2项那个.这个就要自己想了.
qpow(N-2);
ll ans = 0 ;
for(int i=0;i<7;i++){
ans += ( res.a[i][0] * s[i] );
ans %= mod;
}
cout << ans << endl;
}
}
还有一道跟这道好题很相似的题(也是也一道好题!)链接在此
