题解：P15921 [TOPC 2023] Exponentiation

· · 题解

题解：P15921 [TOPC 2023] Exponentiation

思路

我们记 s_i=x^i+x^{-i}。我们化身拉玛努金，考虑如下式子。

s_{i-1}+s_{i+1}=x^{i-1}+x^{-(i-1)}+x^{i+1}+x^{-(i+1)}=(x+x^{-1})(x^i+x^{-i})

由题目我们可以知道 x+x^{-1}=\alpha。所以 s_{i+1}+s_{i-1}=\alpha s_i，s_{i+1}=\alpha s_i-s_{i-1}。由这个式子我们可以得到 s_i 的递推式 s_i=\alpha s_{i-1}-s_{i-2}。由于 \beta 有可能很大，所以我们考虑矩阵快速幂，将上面的递推式写成矩阵的形式。

\begin{bmatrix} s_i\\ s_{i-1} \end{bmatrix}= \begin{bmatrix} \alpha&-1\\ 1&0 \end{bmatrix} \begin{bmatrix} s_{i-1}\\ s_{i-2} \end{bmatrix}

也就是

\begin{bmatrix} s_{\beta}\\ s_{\beta-1} \end{bmatrix}= \begin{bmatrix} \alpha&-1\\ 1&0 \end{bmatrix}^{\beta-1} \begin{bmatrix} s_{1}\\ s_{0} \end{bmatrix}

因为答案实在过大，记得开 __uint128_t，将矩阵中的负数改成与其同余的一个正数。

AC Code

::::success[Code]

#include<bits/stdc++.h>
using namespace std;
#define int __uint128_t
inline int read(){
    int x=0,y=0;char c=0;
    while(!isdigit(c))y|=c=='-',c=getchar();
    while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return y?-x:x;
}
inline void write(int x){
    if(x>9) write(x / 10);
    putchar(x % 10 + '0');
}
int n,k,mod;
struct matrix{
    int a[50][50],r,l;
    matrix(){
        l=0,r=0;
        memset(a,0,sizeof(a));
    }
    void build(){
        for(int i=1;i<=r;i++)a[i][i]=1;
    }
    matrix mul(matrix x){
        matrix y;
        y.r=r;
        y.l=x.l;
        for(int i=1;i<=r;i++){
            for(int j=1;j<=x.l;j++){
                for(int k=1;k<=l;k++){
                    y.a[i][j]+=a[i][k]*x.a[k][j];
                    y.a[i][j]=(y.a[i][j]%mod+mod)%mod;
                }
            }
        }
        return y;
    }
}p,q;
matrix qpow(matrix a,int b){
    matrix ans;
    ans.l=2,ans.r=2;
    ans.build();
    while(b){
        if(b&1)ans=ans.mul(a);
        a=a.mul(a);
        b=b>>1;
    }
    return ans;
}
signed main(){
    k=read(),n=read(),mod=read();
    if(n==0){
        cout<<2;
        return 0;
    }
    p.r=p.l=q.r=2;
    q.l=1;
    p.a[1][1]=k;p.a[1][2]=mod-1;p.a[2][1]=1;
    q.a[1][1]=k;q.a[2][1]=2;
    p=qpow(p,n-1);
    p=p.mul(q);
    write(p.a[1][1]);
    return 0;
}

::::