2020牛客寒假算法基础集训营1 u's的影响力 (矩阵快速幂跑斐波拉契)

之前遇到矩阵斐波拉契没了解过，现在算是稍微理解了点。

前置知识：

1. 斐波拉契通项：
   $f\left[n\right]=f[n-1]+f[n-2],n\ge 3$f[n]=f[n−1]+f[n−2],n≥3
2. 斐波拉契——矩阵形式
   由于：
   [f[2]f[3]​]=[01​11​][f[1]f[2]​]
   递推一下可得矩阵形式通项：
   [f[n]f[n+1]​]=[01​11​]n−1[f[1]f[2]​]

题意： $f\left(1\right)=x,f\left(2\right)=y,$f(1)=x,f(2)=y, 之后每一项等于前两项乘积再乘上 $a^b$ab。
现在问你 $f\left(n\right)\%(10^9+7)$f(n)%(109+7)的结果

题解： 手写几项不难发现 $x$x 和 $y$y的幂都是斐波拉契项， $a$a的幂是前两项幂之和加 $1$1。
由于n $\in [1,10^{12}]$∈[1,1012]，所以无法递推斐波拉契的通项得到结果，但是观察可得斐波拉契的矩阵形式可得通过矩阵快速幂得到矩阵形式的斐波拉契之后取得矩阵中的 $f\left[n\right]$f[n]即可。
由于幂次也过大，所以先可以将取模，由费马小定理 $a^{p-1}\equiv 1\left(modp\right)，p$ap−1≡1(mod p)，p为质数，
故我们的幂只需mod $(10^9+6)$(109+6)即可

$a$a的幂的矩阵形式：
⎣⎡​f[n]f[n+1]1​⎦⎤​=⎣⎡​010​110​011​⎦⎤​n−1⎣⎡​f[1]f[2]1​⎦⎤​

代码：

#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;
typedef long long ll;
 
struct M{
    ll m[3][3];
    void init() {
        for(int i = 0; i < 3; i++)  
            for(int j = 0; j < 3; j++)
                m[i][j] = 0;
    }
};
 
 //Martix mutiplication
M cal(M a, M b, ll mod){
    M res;
    for(int i = 0; i < 3; i++)
        for(int j = 0; j < 3; j++){
            res.m[i][j] = 0;
            for(int k = 0; k < 3; k++){
                res.m[i][j] += a.m[i][k] * b.m[k][j] % mod;
                res.m[i][j] %= mod;
            }
        }
    return res;
}
 
 //Martix quick_pow
M quick_pow(M a, ll b, ll mod){
    M res; res.init();
     
    res.m[0][0] = res.m[1][1] = res.m[2][2] = 1;
     
    while(b) {
        if(b & 1) res = cal(res, a, mod);
        a = cal(a, a, mod);
        b >>= 1;
    }
    return res;
}
 
 //quick_pow
ll qp_num(ll a, ll b, ll mod){
    ll ans = 1 % mod;
    while(b) {
        if(b & 1) ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}
 
 //Martix fibonacci
ll fib(ll n, ll mod) {
    M temp; temp.init();
    temp.m[0][1] = temp.m[1][1] = temp.m[1][0] = temp.m[1][2] = 1;
     
    temp = quick_pow(temp, n - 1, mod);
    return (temp.m[0][0] + temp.m[0][1]) % mod;
}
 
 //Martix fib_variant
ll fib2(ll n, ll mod) {
    M temp; temp.init();
    temp.m[0][1] = temp.m[1][1] = temp.m[1][0] = temp.m[1][2] = temp.m[2][2] = 1;
     
    temp = quick_pow(temp, n - 1, mod);
    return (temp.m[0][0] + 2 * temp.m[0][1] + temp.m[0][2]) % mod; 
    //fib2[2] = 2
}
 
int main()
{
    ll n, x, y, a, b;
    scanf("%lld%lld%lld%lld%lld", &n, &x, &y, &a, &b);
    if(n == 1) printf("%lld\n", x % mod);
    else if(n == 2) printf("%lld\n", y % mod);
    else if(x % mod == 0 || y % mod == 0 || a % mod == 0) printf("0\n");
    
    else {
        x %= mod; y %= mod; a = qp_num(a % mod, b, mod);//a = a^b
        ll ans = qp_num(x, fib(n - 2, mod - 1), mod) * qp_num(y, fib(n - 1, mod - 1), mod) % mod;
        //ans = x^fib(n - 2) * y^fib(n-1)
        
        ans = ans * qp_num(a, fib2(n - 2, mod - 1) % (mod - 1), mod) % mod;
       	//ans = ans * a^fib2(n-2)
       
        printf("%lld\n", ans);
    }
     
    return 0;
}