E - Geometric Progression

https://atcoder.jp/contests/abc293/tasks/abc293_e

思路

根据矩阵递推式

找出转移矩阵的幂形式。

利用矩阵快速幂计算。

Code

https://atcoder.jp/contests/abc293/submissions/39950916

#include <bits/stdc++.h>
using namespace std;
long long mod;
#define ll long long

struct M{
    ll m[2][2];
};

M operator*(M a,M b){
    M ans={{0}};
    
    for(int i=0;i<2;i++){
        for(int j=0;j<2;j++){
            for(int k=0;k<2;k++){
                ans.m[i][j]+=a.m[i][k]*b.m[k][j];
                ans.m[i][j]%=mod;
            }
        }
    }
    return ans;
} 
M ksm(M a,ll b){
    M ans{.m={{1,0},{0,1}}};
    while (b>0){
        if(b&1)ans=ans*a;
        a=a*a;
        b>>=1;
    }
    return ans;
} 
int main(){
    long long a,k;
    cin>>a>>k>>mod;
    M tmp{.m={{1,a},{0,a}}};
    M s{.m={{1,0},{1,0}}};
    M ans=ksm(tmp,k-1)*s;
    cout<<ans.m[0][0]%mod<<endl;
}