ACM模板库

ACM模板库


十进制矩阵快速幂

#include <iostream>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
struct Max{
    ll a[5][5];
    Max operator*(const Max &m){
        Max M;
        for(int i = 1; i <= 2; i++){
            for(int j = 1; j <= 2; j++){
                ll sum = 0;
                for(int k = 1; k <= 2; k++){
                    sum = (sum + this->a[i][k] * m.a[k][j] % mod) % mod;
                }
                M.a[i][j] = sum;
            }
        }
        return M;
    }
    Max(){
        this->a[1][1] = this->a[2][2] = 1;
        this->a[1][2] = this->a[2][1] = 0;
    }
};
Max qpow(Max a, string s){
    Max m;
    int n = s.size() - 1;
    while(n >= 0){
        int b = s[n] - '0';
        for(int i = 1; i <= b; i++)
            m = m * a;
        a = a * a;
        Max y = a * a;
        Max z = y * y;
        a = a * z;
        n--;
    }
    return m;
}

页面列表

ITEM_HTML