牛客小白月赛13_A_小A的签到题

佚名 6年前 (2019-04-12) 随笔 1062人围观抢沙发百度已收录

矩阵快速幂裸题。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Matrix{
    long long a[2][2];
    Matrix(){
        memset(a,0,sizeof(a));
    }
}; 
Matrix operator * (Matrix A,Matrix B){
    Matrix ret;
    for (int i = 0;i < 2;++i){
        for (int j = 0;j < 2;++j){
            for (int k = 0;k < 2;++k){
                ret.a[i][j] += A.a[i][k] * B.a[k][j];
            }
        }
    }
    return ret;
}

Matrix operator ^ (Matrix A,ll n){
    Matrix ret;
    for (int i = 0;i < 2;++i){
        for (int j = 0;j < 2;++j){
            ret.a[i][j] = 1;
        }
    }
    while(n){
        if (n&1) ret = ret * A;
        A = A * A;
        n >>= 1; 
    }
    return ret;
}

int main(){
    ll n;
    scanf("%lld",&n);
    Matrix A;
    A.a[0][0] = 0;
    A.a[0][1] = A.a[1][0] = A.a[1][1] = 1;
    A = A ^ n;
    ll f1 = A.a[0][1];
    ll f2 = A.a[1][0] + A.a[1][1];
    printf("%lld\n",f1 * f1 + f1 * f2 - f2 * f2);
}