OI

【模板】快速幂、矩阵快速幂

快速幂

long long内快速幂

1
2
3
4
5
6
7
8
9
10
typedef long long ll;
ll Fast_Power(ll a, ll b,ll mod){
    ll ans = 1, base = a;
    while(b != 0){
        if(b & 1)ans *= base;
        base *= base;
        b >>= 1;
    }
    return ans;
}

long long内快速幂取模

1
2
3
4
5
6
7
8
9
10
11
typedef long long ll;
ll Fast_Power_mod(ll a, ll b,ll mod){
    ll ans = 1, base = a;
    while(b != 0){
        if(b & 1)ans = (ans*base)%mod;
        base = (base*base)%mod;
        b >>= 1;
    }
    ans%=mod;//一定要有
    return ans;
}

高精度快速幂

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
63
64
65
66
67
68
69
70
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
const int MAX=36000;
struct num{
    char n[MAX];    //number of int(not char!)
    int len;        //length
};

inline void mul(num &a,num &b,num &ans){
    int i,j,jw;
    num c;
    memset(c.n,0,sizeof(c.n));
    for(i=0;i<a.len;i++){
        jw=0;
        for(j=0;j<b.len;j++){
            c.n[i+j]=a.n[i]*b.n[j]+jw+c.n[i+j];
            jw=c.n[i+j]/10;
            c.n[i+j]%=10;
        }
        c.n[i+j]=jw;
    }

    c.len=a.len+b.len;
    while(c.n[c.len-1]==0&&c.len>1)c.len--;
    ans=c;
}


inline void numcpy(num &a,long long x){
    memset(a.n,0,sizeof(a.n));
    if(x==0){
        a.len=1;
        return;
    }
    a.len=0;
    while(x!=0){
        a.n[a.len]=x%10;
        x/=10;
        a.len++;
    }
}

inline void pnum(num &a){              //put number
    for(int i=a.len-1;i>=0;i--)
        printf("%d",a.n[i]);
    printf("\n");
}

num Fast_Power(ll a, ll b){
    num ans, base;
    numcpy(ans,1);
    numcpy(base,a);
    while(b != 0){
        if(b & 1)mul(ans,base,ans);
        mul(base,base,base);
        b >>= 1;
    }
    return ans;
}

int main(){
    int a,b;
    scanf("%d%d",&a,&b);
    num t=Fast_Power(a,b);
    pnum(t);
    return 0;
}

矩阵快速幂

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
typedef long long ll;
const ll MAXN=105,MOD=1000000007;
ll n,k;
struct mat{
    ll m[MAXN][MAXN];
    mat(){}
    mat(bool e){
        memset(m,0,sizeof(m));
        if(e)for(int i=0;i<n;i++)m[i][i]=1;
    }
};
mat a;

mat mul(const mat &a,const mat &b){
    mat c(0);
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            for(int k=0;k<n;k++)
                c.m[i][j]=(c.m[i][j]%MOD+(a.m[i][k]%MOD)*(b.m[k][j]%MOD))%MOD;
    return c;
}

mat fp(const mat &a,ll b){
    mat ans(1),base=a;
    while(b!=0){
        if(b&1)ans=mul(ans,base);
        base=mul(base,base);
        b>>=1;
    }
    return ans;
}

快速幂求斐波那契数列

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
#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
ll t[3][3]={{1,1},
             {1,0}};
ll MOD=1000000007;
void mul(ll a[][3],ll b[][3]){
    ll tmp[3][3]={0};
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            for(int k=0;k<2;k++){
                tmp[i][j]+=(a[i][k]%MOD)*(b[k][j]%MOD)%MOD;
                tmp[i][j]%=MOD;
            }
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            a[i][j]=tmp[i][j]%MOD;
}

void fp(ll a[][3],ll n){
    ll res[3][3]={{1,0},
                   {0,1}};
    while(n){
        if(n&1)mul(res,a);
        mul(a,a);
        n>>=1;
    }
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            a[i][j]=res[i][j]%MOD;
}

int main(){
    ll n;
    scanf("%lld",&n);
    fp(t,n);
    printf("%lld",t[0][1]);
    return 0;
}