快速幂 + 矩阵快速幂

快速幂    

#include<iostream>
#include<algorithm>
#include<cstring>
#define LL long long
using namespace std;

LL Pow(LL a, LL b)
{
    LL ans = 1;
    while(b != 0){
        if(b&1)
            ans *= a;
        a *= a;
        b >>= 1;
    }
    return ans;
}
int main()
{
    LL a, b;
    cin >> a >> b; 
    cout << Pow(a,b) << endl;
    return 0;
}

#include<iostream>
#include<algorithm>
#include<cstring>
#define LL long long
using namespace std;
const LL mod = 1e9+7;

LL Pow(LL a, LL b)
{
    LL ans = 1;
    while(b != 0){
        if(b&1){
            ans *= a;
            ans %= mod;
        }
        a *= a;
        a %= mod;
        b >>= 1;
    }
    return ans;
}
int main()
{
    LL a, b;
    cin >> a >> b; 
    cout << Pow(a,b) << endl;
    return 0;
}

矩阵快速幂

   模板！ （自己敲了一遍 只是感觉有些乱 就把ff的记上

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long LL;
const int N = 105;
const LL mod = 1e9 + 7;
LL n, m;
struct mac {
    LL c[N][N];
    void reset() {
        memset(c, 0, sizeof(c));
        for (int i = 1; i <= n; i++)
            c[i][i] = 1;
    }
};
mac multi(mac a, mac b) 
{
    mac ans;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            ans.c[i][j] = 0;
            for (int k = 1; k <= n; k++) {
                ans.c[i][j] += (a.c[i][k] * b.c[k][j]) % mod;
                ans.c[i][j] %= mod;
            }
        }
    return ans;
}
mac Pow(mac a, LL b) 
{
    mac ans; ans.reset();
    while (b) {
        if (b & 1) 
            ans = multi(ans, a);
        a = multi(a, a);
        b >>= 1;
    }
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    while (cin >> n >> m) {
        mac a;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                cin >> a.c[i][j];
        a = Pow(a, m);
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j < n; j++)
                cout << a.c[i][j] << " ";
            cout << a.c[i][n] << endl;
        }
    }
    return 0;
}

[应用]（矩阵快速幂

4267: 二元数列

时间限制: 1 Sec  内存限制: 128 MB

题目描述

已知:


输入x0,y0,a,b,c,d,n
输出xn，yn对20181225取模的结果

输入

输入x0,y0,a,b,c,d,n

输出

输出xn，yn对20181225取模的结果

样例输入

7 6 5 4 3 2 1

样例输出

59 33

提示

0<=x0,y0,a,b,c,d<=1e3

0<=n<=8e8

解：虽然我此时此刻很想打死旁边的猪 可是不得不承认这个题 ，是他教的

　      先推出 Xn+1 = (a²+bc)Xn-1 + (ab+bd)Yn-1;

　　     　　  Yn+1 = (ac+cd)Xn-1 + (bc+d²)Yn-1;        取系数为一个矩阵，你就会发现系数是由Xn Yn系数的平方求来的， 然后推推就知道  题目求是一个矩阵的n次方  由于n太大，所以采用矩阵快速幂来求出最后Xn Yn的系数，最后求得答案。

#include<iostream>
#include<algorithm>
#include<cstring>
#define LL long long
using namespace std;
const LL mod = 20181225;
struct node{
    LL m[2][2];
    void reset(){
        memset(m,0,sizeof(m));
        m[0][0] = 1;
        m[1][1] = 1;
    }
};
LL xx, yy, a, b, c, d, n, x, y;

node multi(node a, node b)
{
    node ans; ans.reset();
    ans.m[0][0] = 0; ans.m[1][1] = 0;
    for(int i = 0; i < 2; i++)
        for(int j = 0; j < 2; j++)
            for(int k = 0; k < 2; k++){
            ans.m[i][j] += (a.m[i][k] * b.m[k][j]) % mod;
            ans.m[i][j] %= mod;
    }
    return ans;
}
node Pow(node a, LL b)
{
    node ans; ans.reset();
    while(b){
        if(b & 1)
            ans = multi(ans, a);
        a = multi(a, a);
        b >>= 1;
    }
    return ans;
}
int main()
{
    node may;
    while(cin >> xx >> yy >> a >> b >> c >> d >> n){
        may.m[0][0] = a; may.m[0][1] = b;
        may.m[1][0] = c; may.m[1][1] = d;
        may = Pow(may,n);
        x = (may.m[0][0] * xx + may.m[0][1] * yy) % mod;
        y = (may.m[1][0] * xx + may.m[1][1] * yy) % mod;
        cout << x << " " << y << endl;
    }
    return 0;
} 

[后记]   啦啦啦 这是我的第一篇博客，写给自己看的博客， 以后要找些什么也会方便很多！ 做个总结。希望这十分钟不是浪费，加油鸭 小菜鸟 哈哈哈哈哈  虽然我感觉8 这条道路上的大佬超级多，但是！ 好像不是但是，我是一个比较容易放弃的人哈哈哈 也可以记录一下生活呀 什么的 对伐！ 耶  悄咪咪的