题解：P15921 [TOPC 2023] Exponentiation

· · 题解

这道题弱化版（有别于数据范围与输入顺序）：P9777

设 f_i = x^i + x^{-i}。

因为题目给出了 f_1 的答案为 \alpha，我们希望将它与 f_i\ (i\geq 2) 建立联系（从 f_i 中拆出 f_1）。

f_i &= x^i + x^{-i} \\ &= x^{i-1} \times x + x^{1-i} \times x^{-1} \\ &= (x^{i-1} + x^{1-i})(x+x^{-1}) - x^{i-1}\times x^{-1} - x^{1-i} \times x \\ &= (x^{i-1} + x^{1-i})(x+x^{-1}) - (x^{i-2} + x^{2-i}) \\ &= f_{i-1} \times f_1 - f_{i-2} \\ &= \alpha f_{i-1} - f_{i-2} \end{aligned}

为什么会想到这么做呢（指第三步）？因为这十分类似十字相乘。

于是我们得到了 f 的递推公式，所以可以使用矩阵加速：

f_i = \begin{cases} 2&,i = 0 \\ \alpha&,i = 1 \\ \alpha f_{i-1} - f_{i-2}&,i\ge2 \end{cases}

令初始矩阵 T = \begin{bmatrix}f_0\\f_1\end{bmatrix} = \begin{bmatrix}2\\\alpha\end{bmatrix}，转移矩阵 A = \begin{bmatrix}0&1\\-1&\alpha\end{bmatrix} = \begin{bmatrix}0&1\\m-1&\alpha\end{bmatrix}（-1 \equiv m-1 \pmod m，这题数据太大导致 __int128 都存不了，只能用 unsigned __int128。），

则答案矩阵 ans = A^{\beta - 1} \times T，f_{\beta} = ans_{2,1}。

#include<iostream>
#include<cstdio>
#include<cstring>
#define re register
#define endl '\n'
#define ll unsigned __int128
#define ull unsigned long long
#define db double
#define fi const int&
#define fl const ll&
#define ful const ull&
#define fc const char&
#define fs const string&
#define debug() puts("I Love Hina Forever")
using namespace std ;
namespace IO {
    template<class T>inline void read(T &x){char c=getchar(),f=false;x=0;while(c<48||c>57) {f|=(c==45),c=getchar();}while(c>=48&&c<=57){x=(x<<3)+(x<<1)+(c^48),c=getchar();}if(f){x=~x+1;}}
    template<class T,class ...Arg>inline void read(T &x,Arg &...arg){read(x),read(arg...);}
    template<class T>inline void write(T x){if(x<0){putchar(45),x=~x+1;}if(x>9){write(x/10);}putchar(x%10|48);}
    template<class T>inline void write(T x,fc c){write(x),putchar(c);}
}using namespace IO ;
const int N = 5 ;
ll a,b,m ;
struct matrix {
    int n,m ;
    ll a[N][N] ;
    inline matrix () {memset(a,0,sizeof a) ;}
    inline void prepare (fi _n,fi _m) {n = _n,m = _m ;}
};
inline matrix operator * (matrix A,matrix B) {
    matrix C ;
    C.prepare(A.n,B.m) ;
    for (re int i = 1 ; i <= C.n ; ++i) {
        for (re int j = 1 ; j <= C.m ; ++j) {
            for (re int k = 1 ; k <= A.m ; ++k) (C.a[i][j] += A.a[i][k] * B.a[k][j] % m) %= m ;
        }
    }
    return C ;
}
inline matrix operator ^ (matrix A,ll k) {
    matrix ans ;
    ans.prepare(A.n,A.m) ;
    for (re int i = 1 ; i <= ans.n ; ++i) ans.a[i][i] = 1 ;
    while (k) {
        if (k & 1) ans = ans * A ;
        k >>= 1,A = A * A ;
    }
    return ans ;
}

inline ll f (fl x) {
    matrix A,ans ;
    ans.prepare(2,1) ;
    A.prepare(2,2) ;
    ans.a[1][1] = 2,ans.a[2][1] = a ;
    A.a[1][1] = 0,A.a[1][2] = 1 ;
    A.a[2][1] = m - 1,A.a[2][2] = a ;
    ans = (A ^ (x - 1)) * ans ;
    return ans.a[2][1] ;
}
int main () {
    read(a,b,m) ;
    write(f(b)) ;
    return 0 ;
}