题解：P9777 [HUSTFC 2023] Fujisaki 讨厌数学

· · 题解

首先看眼式子。x+x^{-1}，等等，这不昨天做的数学题吗？

关于这个式子的递推有一个很常用的技巧。我们考虑平方这个式子：

我们可以尝试把这个规律拓展一下。设 $f_i=x^i+x^{-i}$。 $$f_if_1=(x^i+x^{-i})(x+x^{-1})=x^{i+1}+x^{-(i+1)}+x^{i-1}+x^{-(i-1)}=f_{i+1}+f_{i-1} kf_i=f_{i+1}+f_{i-1},f_{i+1}=kf_{i}-f_{i-1}

不对，这是什么？？？递推式，系数与 i 无关，正解 O(\log n)？？？？

这不矩阵快速幂吗。然后问题就变成了矩阵咋推。

我们考虑矩阵 G，使：

f_{i-1} & f_{i-2} \end{bmatrix}G=\begin{bmatrix} f_i & f_{i-1} \end{bmatrix}

一列一列的填。第一列，我们有 f_{i}=kf_{i-1}-f_{i-2}，系数依次填进去，然后 f_{i-1} 就是 f_{i-1}，不用递推：

k & 1\\ -1 & 0 \end{bmatrix}

然后写个矩阵快速幂。注意 n 很小的情况。

代码：

#include <bits/stdc++.h>
#define ll long long
#define db double
#define ull unsigned long long
#define inf INT_MAX
#define linf LLONG_MAX
#define ninf INT_MIN
#define nlinf LLONG_MIN
#define mod m
#define lwbd lower_bound
#define upbd upper_bound
//#define range
using namespace std;
void read(int &x){
    cin >> x;
    return;
}
void readll(ll &x){
    cin >> x;
    return;
}void readdb(db &x){
    cin >> x;
    return;
}
ll n, m, a;
struct matrix{
    ll col, row;
    ll mat[100][100];
    matrix(ll x, ll y){
        col = y;
        row = x;
        for(int i = 0; i < x; i++){
            for(int j = 0; j < y; j++){
                mat[i][j] = 0;
            }
        }
    }
    matrix operator *(matrix p){
        matrix res(row, p.col);
        for(int i = 0; i < res.row; i++){
            for(int j = 0; j < res.col; j++){
                for(int k = 0; k < col; k++){
                    res.mat[i][j] += mat[i][k] * p.mat[k][j] % mod;
                    res.mat[i][j] %= mod;
                }
            }
        }
        return res;
    }
    matrix operator +(matrix p){
        matrix res(row, col);
        for(int i = 0; i < res.row; i++){
            for(int j = 0; j < res.col; i++){
                res.mat[i][j] = mat[i][j] + p.mat[i][j];
                res.mat[i][j] %= mod;
            }
        }
        return res;
    }
    matrix unit(ll x){
        matrix p(x, x);
        for(int i = 0; i < x; i++){
            p.mat[i][i] = 1;
        }
        return p;
    }
};
matrix qpow(matrix p, ll q){
    if(q == 0){
        return p.unit(p.col);
    }
    if(q == 1){
        return p;
    }
    matrix res = qpow(p, q / 2);
    if(q % 2){
        return res * res * p;
    }
    return res * res;
}
//如果再忘记把题目给的1~n变为0~n-1自罚20仰卧起坐
int main(){
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> m >> a >> n;
    if(n == 0){
        cout << 2 << endl;
    }
    if(n == 1){
        cout << a % mod << endl;
    }
    if(n == 2){
        cout << (a * a - 2) % mod << endl;
    }
    if(n < 3){
        return 0;
    }
    matrix p(2, 2), q(1, 2);
    q.mat[0][0] = (a * a - 2) % mod;
    q.mat[0][1] = a;
    p.mat[0][0] = a;
    p.mat[0][1] = 1;
    p.mat[1][0] = m - 1;
    matrix ans = q * qpow(p, n - 2);
    cout << ans.mat[0][0] << endl;
    return 0;
}